Finding height in Binary Search Tree
AlgorithmRecursionBinary Search-TreeAlgorithm Problem Overview
I was wondering if anybody could help me rework this method to find the height of a binary search tree. So far, my code looks like this. However, the answer I'm getting is larger than the actual height by 1. But when I remove the +1 from my return statements, it's less than the actual height by 1. I'm still trying to wrap my head around recursion with these BST. Any help would be much appreciated.
public int findHeight(){
if(this.isEmpty()){
return 0;
}
else{
TreeNode<T> node = root;
return findHeight(node);
}
}
private int findHeight(TreeNode<T> aNode){
int heightLeft = 0;
int heightRight = 0;
if(aNode.left!=null)
heightLeft = findHeight(aNode.left);
if(aNode.right!=null)
heightRight = findHeight(aNode.right);
if(heightLeft > heightRight){
return heightLeft+1;
}
else{
return heightRight+1;
}
}
Algorithm Solutions
Solution 1 - Algorithm
The problem lies in your base case.
"The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only a node (the root) has a height of zero." - Wikipedia
If there is no node, you want to return -1 not 0. This is because you are adding 1 at the end.
So if there isn't a node, you return -1 which cancels out the +1.
int findHeight(TreeNode<T> aNode) {
if (aNode == null) {
return -1;
}
int lefth = findHeight(aNode.left);
int righth = findHeight(aNode.right);
if (lefth > righth) {
return lefth + 1;
} else {
return righth + 1;
}
}
Solution 2 - Algorithm
The height of a binary search tree is equal to number of layers - 1.
See the diagram at http://en.wikipedia.org/wiki/Binary_tree
Your recursion is good, so just subtract one at the root level.
Also note, you can clean up the function a bit by handling null nodes:
int findHeight(node) {
if (node == null) return 0;
return 1 + max(findHeight(node.left), findHeight(node.right));
}
Solution 3 - Algorithm
int getHeight(Node node) {
if (node == null) return -1;
return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}
Solution 4 - Algorithm
In my opinion, your code would benefit from being simplified a bit. Rather than attempting to end the recursion when a child pointer is null, only end it when the current pointer is null. That makes the code a lot simpler to write. In pseudo-code, it looks something like this:
if (node = null)
return 0;
else
left = height(node->left);
right = height(node->right);
return 1 + max(left, right);
Solution 5 - Algorithm
class Solution{
public static int getHeight(Node root) {
int height = -1;
if (root == null) {
return height;
} else {
height = 1 + Math.max(getHeight(root.left), getHeight(root.right));
}
return height;
}
Solution 6 - Algorithm
For people like me who like one line solutions:
public int getHeight(Node root) {
return Math.max(root.left != null ? getHeight(root.left) : -1,
root.right != null ? getHeight(root.right) : -1)
+ 1;
}
Solution 7 - Algorithm
Here's a concise and hopefully correct way to express it:
private int findHeight(TreeNode<T> aNode){
if(aNode == null || (aNode.left == null && aNode.right == null))
return 0;
return Math.max(findHeight(aNode.left), findHeight(aNode.right)) + 1;
}
If the current node is null, there's no tree. If both children are, there's a single layer, which means 0 height. This uses the definition of height (mentioned by Stephen) as # of layers - 1
Solution 8 - Algorithm
This is untested, but fairly obviously correct:
private int findHeight(Treenode<T> aNode) {
if (aNode.left == null && aNode.right == null) {
return 0; // was 1; apparently a node with no children has a height of 0.
} else if (aNode.left == null) {
return 1 + findHeight(aNode.right);
} else if (aNode.right == null) {
return 1 + findHeight(aNode.left);
} else {
return 1 + max(findHeight(aNode.left), findHeight(aNode.right));
}
}
Often simplifying your code is easier than figuring out why it's off by one. This code is easy to understand: the four possible cases are clearly handled in an obviously correct manner:
- If both the left and right trees are null, return 0, since a single node by definition has a height of 0. (was 1)
- If either the left or right trees (but not both!) are null, return the height of the non-null tree, plus 1 to account for the added height of the current node.
- If neither tree is null, return the height of the taller subtree, again plus one for the current node.
Solution 9 - Algorithm
public void HeightRecursive()
{
Console.WriteLine( HeightHelper(root) );
}
private int HeightHelper(TreeNode node)
{
if (node == null)
{
return -1;
}
else
{
return 1 + Math.Max(HeightHelper(node.LeftNode),HeightHelper(node.RightNode));
}
}
C# code. Include these two methods in your BST class. you need two method to calculate height of tree. HeightHelper calculate it, & HeightRecursive print it in main().
Solution 10 - Algorithm
The definition given above of the height is incorrect. That is the definition of the depth.
"The depth of a node M in a tree is the length of the path from the root of the tree to M. The height of a tree is one more than the depth of the deepest node in the tree. All nodes of depth d are at level d in the tree. The root is the only node at level 0, and its depth is 0."
Citation: "A Practical Introduction to Data Structures and Algorithm Analysis" Edition 3.2 (Java Version) Clifford A. Shaffer Department of Computer Science Virginia Tech Blacksburg, VA 24061
Solution 11 - Algorithm
public int height(){
if(this.root== null) return 0;
int leftDepth = nodeDepth(this.root.left, 1);
int rightDepth = nodeDepth(this.root.right, 1);
int height = leftDepth > rightDepth? leftDepth: rightDepth;
return height;
}
private int nodeDepth(Node node, int startValue){
int nodeDepth = 0;
if(node.left == null && node.right == null) return startValue;
else{
startValue++;
if(node.left!= null){
nodeDepth = nodeDepth(node.left, startValue);
}
if(node.right!= null){
nodeDepth = nodeDepth(node.right, startValue);
}
}
return nodeDepth;
}
Solution 12 - Algorithm
//function to find height of BST
int height(Node* root) {
if(root == NULL){
return -1;
}
int sum=0;
int rheight = height(root->right);
int lheight = height(root->left);
if(lheight>rheight){
sum = lheight +1;
}
if(rheight > lheight){
sum = rheight + 1;
}
return sum;
}
Solution 13 - Algorithm
int height(Node* root) {
if(root==NULL) return -1;
return max(height(root->left),height(root->right))+1;
}
Take of maximum height from left and right subtree and add 1 to it.This also handles the base case(height of Tree with 1 node is 0).
Solution 14 - Algorithm
I know that I’m late to the party. After looking into wonderful answers provided here, I thought mine will add some value to this post. Although the posted answers are amazing and easy to understand however, all are calculating the height to the BST in linear time. I think this can be improved and Height can be retrieved in constant time, hence writing this answer – hope you will like it. Let’s start with the Node class:
public class Node
{
public Node(string key)
{
Key = key;
Height = 1;
}
public int Height { get; set; }
public string Key { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
public override string ToString()
{
return $"{Key}";
}
}
BinarySearchTree class
So you might have guessed the trick here… Im keeping node instance variable Height to keep track of each node when added. Lets move to the BinarySearchTree class that allows us to add nodes into our BST:
public class BinarySearchTree
{
public Node RootNode { get; private set; }
public void Put(string key)
{
if (ContainsKey(key))
{
return;
}
RootNode = Put(RootNode, key);
}
private Node Put(Node node, string key)
{
if (node == null) return new Node(key);
if (node.Key.CompareTo(key) < 0)
{
node.Right = Put(node.Right, key);
}
else
{
node.Left = Put(node.Left, key);
}
// since each node has height property that is maintained through this Put method that creates the binary search tree.
// calculate the height of this node by getting the max height of its left or right subtree and adding 1 to it.
node.Height = Math.Max(GetHeight(node.Left), GetHeight(node.Right)) + 1;
return node;
}
private int GetHeight(Node node)
{
return node?.Height ?? 0;
}
public Node Get(Node node, string key)
{
if (node == null) return null;
if (node.Key == key) return node;
if (node.Key.CompareTo(key) < 0)
{
// node.Key = M, key = P which results in -1
return Get(node.Right, key);
}
return Get(node.Left, key);
}
public bool ContainsKey(string key)
{
Node node = Get(RootNode, key);
return node != null;
}
}
Once we have added the key, values in the BST, we can just call Height property on the RootNode object that will return us the Height of the RootNode tree in constant time. The trick is to keep the height updated when a new node is added into the tree. Hope this helps someone out there in the wild world of computer science enthusiast!
Unit test:
[TestCase("SEARCHEXAMPLE", 6)]
[TestCase("SEBAQRCHGEXAMPLE", 6)]
[TestCase("STUVWXYZEBAQRCHGEXAMPLE", 8)]
public void HeightTest(string data, int expectedHeight)
{
// Arrange.
var runner = GetRootNode(data);
// Assert.
Assert.AreEqual(expectedHeight, runner.RootNode.Height);
}
private BinarySearchTree GetRootNode(string data)
{
var runner = new BinarySearchTree();
foreach (char nextKey in data)
{
runner.Put(nextKey.ToString());
}
return runner;
}
Note: This idea of keeping the Height of tree maintained in every Put operation is inspired by the Size of BST method found in the 3rd chapter (page 399) of Algorithm (Fourth Edition) book.
Solution 15 - Algorithm
I guess this question could mean two different things...
- Height is the number of nodes in the longest branch:-
int calcHeight(node* root){ if(root==NULL) return 0; int l=calcHeight(root->left); int r=calcHeight(root->right); if(l>r) return l+1; else return r+1; }
2. Height is the total number of nodes in the tree itself:
`int calcSize(node* root){
if(root==NULL)
return 0;
return(calcSize(root->left)+1+calcSize(root->right));
}`
Solution 16 - Algorithm
public int getHeight(Node node)
{
if(node == null)
return 0;
int left_val = getHeight(node.left);
int right_val = getHeight(node.right);
if(left_val > right_val)
return left_val+1;
else
return right_val+1;
}
Solution 17 - Algorithm
Here is a solution in C#
private static int heightOfTree(Node root)
{
if (root == null)
{
return 0;
}
int left = 1 + heightOfTree(root.left);
int right = 1 + heightOfTree(root.right);
return Math.Max(left, right);
}
Solution 18 - Algorithm
Set a tempHeight as a static variable(initially 0).
static void findHeight(Node node, int count) {
if (node == null) {
return;
}
if ((node.right == null) && (node.left == null)) {
if (tempHeight < count) {
tempHeight = count;
}
}
findHeight(node.left, ++count);
count--; //reduce the height while traversing to a different branch
findHeight(node.right, ++count);
}
Solution 19 - Algorithm
Here is a solution in Java a bit lengthy but works..
public static int getHeight (Node root){
int lheight = 0, rheight = 0;
if(root==null) {
return 0;
}
else {
if(root.left != null) {
lheight = 1 + getHeight(root.left);
System.out.println("lheight" + " " + lheight);
}
if (root.right != null) {
rheight = 1+ getHeight(root.right);
System.out.println("rheight" + " " + rheight);
}
if(root != null && root.left == null && root.right == null) {
lheight += 1;
rheight += 1;
}
}
return Math.max(lheight, rheight);
}
Solution 20 - Algorithm
int getHeight(Node* root)
{
if(root == NULL) return -1;
else return max(getHeight(root->left), getHeight(root->right)) + 1;
}
Solution 21 - Algorithm
For anyone else that reads this!!!!
HEIGHT is defined as the number of nodes in the longest path from the root node to a leaf node. Therefore: a tree with only a root node has a height of 1 and not 0.
The LEVEL of a given node is the distance from the root plus 1. Therefore: The root is on level 1, its child nodes are on level 2 and so on.
(Information courtesy of Data Structures: Abstraction and Design Using Java, 2nd Edition, by Elliot B. Koffman & Paul A. T. Wolfgang) - Book used in Data Structures Course I am currently taking at Columbus State University.
Solution 22 - Algorithm
According to "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, following is the definition of tree height:
> The height of a node in a tree is the number of edges on the longest simple downward path from the node to a leaf, and the height of a tree is the height of its root. The height of a tree is also equal to the largest depth of any node in the tree.
Following is my ruby solution. Most of the people forgot about height of empty tree or tree of single node in their implementation.
def height(node, current_height)
return current_height if node.nil? || (node.left.nil? && node.right.nil?)
return [height(node.left, current_height + 1), height(node.right, current_height + 1)].max if node.left && node.right
return height(node.left, current_height + 1) if node.left
return height(node.right, current_height + 1)
end
Solution 23 - Algorithm
int maxDepth(BinaryTreeNode root) {
if(root == null || (root.left == null && root.right == null)) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
Solution 24 - Algorithm
Height of Binary Tree
public static int height(Node root)
{
// Base case: empty tree has height 0
if (root == null) {
return 0;
}
// recursively for left and right subtree and consider maximum depth
return 1 + Math.max(height(root.left), height(root.right));
}
Solution 25 - Algorithm
I struggled with this myself trying to find something elegant that still resulted in the correct value. Here's what I came up with using Swift. Note that height is a computed variable and technically not a function.
class Node<T: Comparable>: NSObject
{
var left: Node<T>? = nil
var right: Node<T>? = nil
var isLeaf: Bool { left == nil && right == nil }
var height: Int {
if isLeaf { return 0 }
return 1 + max(left?.height ?? 0, right?.height ?? 0)
}
}
There's more to this Node definition but you can see the left and right variables (possibly nil) and an isLeaf var that is true when both left and right are nil. Might not be the most efficient but I believe it yields the correct result.
The BST definition also has a computed height variable and returns -1 when the tree is empty.
class BST<T: Comparable>: NSObject
{
var root: Node<T>?
var height: Int { root != nil ? root!.height : -1 }
}
Solution 26 - Algorithm
HackerRank Day 22: Finding height in Binary Search Tree, in C#.
static int getHeight(Node root)
{
//Write your code here
int countr = 0,countl=0;
Node Leftsubtree=root.left;
Node rightsubtree = root.right;
int data=root.data;
if(root==null ||(root.left == null && root.right == null))
{
return 0;
}
else
{
while (Leftsubtree != null)
{
if(Leftsubtree.data<data)
{
Leftsubtree = Leftsubtree.left==null?Leftsubtree.right:Leftsubtree.left;
countl++;
}
}
while (rightsubtree != null)
{
if (rightsubtree.data > data)
{
rightsubtree = rightsubtree.right == null ? rightsubtree.left : rightsubtree.right;
countr++;
}
}
}
return countr >= countl ? countr : countl;
}