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.

Can't you show the BST in its cascaded form? Are you sure the insertion is done correctly? — Willem Van Onsem, Jun 25 '17 at 12:56
@WillemVanOnsem Yes, the insertion is done correctly, I've checked every other part of the code one by one.The only flaw must be in this block. — mathoverflows, Jun 25 '17 at 13:20
This is a simple error in the first line. You are checking if `right == null` AND `right == null`. You probably intended for one of those to be `left`. — Peter Hall, Jun 25 '17 at 13:25
@PeterHall Thanks, Sir. I was scratching my head over this problem for quite a while. — mathoverflows, Jun 25 '17 at 13:29

score 2 · Accepted Answer · answered Jun 25 '17 at 13:28

2

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.

answered Jun 25 '17 at 13:28

Peter Hall

53,120
14
139
204

Thanks for pointing out the bug. – mathoverflows Jun 25 '17 at 13:33

Height of a Binary Search Tree

1 Answers1