Height of a Binary Search Tree

Question

I have written code for calculating the height of a BST, but it's giving me the wrong answer. The result is 3 but I am expecting it to be 4. Can anyone point out the flaw in my logic, please? (I'm defining the height of leaf nodes to be zero, thus height = edge count).

public static int getHeight(Node root){
    if(root == null || (root.right == null && root.right == null)) return 0;
    int leftHeight = getHeight(root.left);
    int rightHeight = getHeight(root.right);
    return 1 + ((leftHeight >= rightHeight) ? leftHeight : rightHeight);
}

The elements are added in an empty BST in the following order:

20, 50, 35, 44, 9, 15, 62, 11, 13

So I expect that it should look like this:

     20
   /    \
  /      \
 9        50
  \      /  \
   15   35   62
  /      \
11       44
  \
   13

Edit: Found the bug. I had written

    (root.right == null && root.right == null)

instead of

    (root.left == null && root.right == null)

Thanks to Peter Hall for pointing it out.

Answer 1

This is a simple typo. You are checking for right == null twice, when you almost certainly meant left == null for one of them.

I.e. this condition:

if(root == null || (root.right == null && root.right == null)) return 0;

Should be:

if(root == null || (root.right == null && root.left == null)) return 0;

Which will give you the answer you want.