CODEWITHSUNDEEP
javarecursionbinary-search-tree
reedaccess_
reedaccess_

Reputation: 80

Why can't I get the height of a BST in one statement (Java)

I was learning about binary search trees, and a practice problem involved recursively finding the height of the tree.

This is the Java code that was accepted:

public static int getHeight(Node root){
        if (root == null)
            return -1;
        else {
            int leftHeight = getHeight(root.left);
            int rightHeight = getHeight(root.right);

            if (leftHeight > rightHeight)
                return leftHeight + 1;
            else
                return rightHeight + 1;
        }
}

And this was the code (given as pseudocode in the tutorial) I tried at first and thought would work:

public static int getHeight(Node root){
     return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}

However when I went to submit the second statement, it gave me a runtime error and NPEs. Is the if (root == null){return -1}; a base case that the second statement doesn't implicitly have?

Upvotes: 1

Views: 54

Answers (2)

Eklavya
Eklavya

Reputation: 18430

Yes, when root is null then root.left is called that's why you are getting NPE.

And recursive function needs a base case which not called the recursive function again. Here, when root is null that means you are calling getHeight() on root.left or root.right where root is leaves of the tree that is the base case.

Upvotes: 1

Adam McCormick
Adam McCormick

Reputation: 1670

@Eklavya has the right answer here, but since you're learning and I love recursion a couple good rules of thumb to add.

  • Always have a termination condition in your code explicitly. Making termination implicit may be clever but communicating it and maintaining it are hard
  • In Java, always assume a value is null in your method unless you have specifically annotated it otherwise. Unprotected child access is always a code smell
  • Best practice in most languages with explicit privacy (like Java) is not to use members directly but to build an interface and reference methods from the interface (root.left() not root.left). It's a bit of pain now, but it will save you thousands of wasted hours if it's a habit you stay in.

Upvotes: 0

Related Questions