Finding height in Binary Search Tree

0 votes
asked Apr 8, 2010 by mike

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;
    }
}

18 Answers

0 votes
answered Jan 8, 2010 by matthew-flaschen

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

0 votes
answered Jan 8, 2010 by jerry-coffin

IMO, you 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);
0 votes
answered Jan 8, 2010 by jemfinch

This is untested, but fairly obviously correct:

private int findHeight(Treenode 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 1, since a single node by definition has a height of 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.
0 votes
answered Apr 8, 2010 by stephen

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));
}
0 votes
answered Apr 8, 2010 by corey

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;
    }
}
0 votes
answered Jan 5, 2011 by desire
    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().

0 votes
answered Jan 9, 2013 by amyers

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

0 votes
answered Jan 11, 2013 by aalyiah7492

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.

0 votes
answered Jan 7, 2014 by vbp

Here is a solution in C#

    private static int height_Tree(Node root)
    {
        if (root == null)
        {
            return 0;
        }

        int left = 1 + height_Tree(root.left);
        int right = 1 + height_Tree(root.right);

        return Math.Max(left, right);
    }
0 votes
answered Jan 13, 2014 by avishek-gurung
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;
}
Welcome to Q&A, where you can ask questions and receive answers from other members of the community.
Website Online Counter

...