Finding height in Binary Search Tree

Question

Hey 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 im getting is larger than the actual height by 1, but when I remove the +1 from my return statements its 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;
    }
}

Answer 1

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

Answer 2

the code looks fine, it's probably an error in the test harness.

Answer 3

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

Answer 4

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

Answer 5

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 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 == 0)
        return -1;

    left = findHeight(aNode.left);
    right = findHeight(aNode.right);

    if(left > right)
        return left + 1;
    else
        return right +1
}