Finding height in Binary Search Tree

Question

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

Answer 1

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