CODEWITHSUNDEEP
javarecursionbinary-search-tree
j bel
j bel

Reputation: 153

Binary Search Tree recursion methods

I have been set the task to search and find the height of a binary search tree. In trying to resolve the issue I came up with the following solution.

static int countL = 0 ;
static int countR = 0 ;
public static int getHeight(Node root) {

    if (root.left != null) {
        countL++;

        getHeight(root.left);
    }

    if (root.right != null) {
        countR++;

        getHeight(root.right);
    }

    count = Math.max(countL, countR);

    return count;
}

Not the most elegant but never the less it resolves the problem for certain trees. Searching the web I have found an alternative solution. Apart from being more elegant code, what is the difference between what I have above to what can be seen below? In the quest of becoming a more proficient coder what is the best way to reduce the lines of code. My quest is to understand where i went wrong and what the code below does different in comparison to mine

private static int getHeight(Node root){
int heightLeft = 0;
int heightRight = 0;

if (root.left != null) {
    heightLeft = getHeight(root.left) + 1;
}
if (root.right != null) {
    heightRight = getHeight(root.right) + 1;
}
return (heightLeft > heightRight ? heightLeft : heightRight);
}

Upvotes: 0

Views: 152

Answers (2)

userg
userg

Reputation: 46

In your first solution, you are incrementing the countL and countR counters without considering the height of the tree you traversed so far. Let’s take for example a skewed tree like below

   1.   => CountL = 1;  CountR = 0
  /.   
 2.     => CountL = 2;  CountR = 0
/ 
3.      => CountL = 3;  CountR = 0
 \
  4.    => CountL = 3; CountR = 1

If you look at the last step while incrementing countR, the height that was covered by traversing the left nodes were ignored.

Your second solution is a bottom-up approach where at each level, we compare both left and right height and return the max of it.

Hope it helps in understanding the difference between both the solutions!

Upvotes: 1

Gamma032
Gamma032

Reputation: 451

1. The implementation is incorrect

Your implementation is actually not correct. It will only work on the first invocation of getHeight, when both countL and countR are 0. This is because static variables are tied to the class, not an object (like non-static variables) or the scope of a function (like the second solution).

Say after calling getHeight the first time, countL is 3 and countR is 4. When you call it a second time, those variables are never reset, so a tree of depth 1 will return 4.

Finally, your solution also fails for getHeight(null).

2. Static variables are an anti-pattern

Where possible, avoid static variables in classes, as they are global state. See this thread for a full explanation.

3. The second solution is easier to read

As you identified, the second solution is easier to read. This is for three reasons:

  1. All the logic is wholly contained in the function, whereas yours uses global state.
  2. The variable naming is better: heightLeft is more semantic than countL.
  3. It's shorter.

If you're interested, here's an even more concise solution:

public int getHeight(Node root) {
        if(root == null){
            return 0;
        }
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }

Best of luck on your Java-learning adventures!

Upvotes: 1

Related Questions