0

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);
}
j bel
  • 153
  • 6
  • 18

2 Answers2

1

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!

Gamma032
  • 441
  • 4
  • 7
  • Thanks, just to confirm, if root == null, would return 0 when we find a leaf from the tree right? – j bel Jan 30 '22 at 12:00
  • @jbel In your code, I think `if (root.left != null)` will throw a `NullPointerException` since `root` is `null` and has no `left` property. – Gamma032 Jan 30 '22 at 12:03
  • Ok yes, this makes sense.. lastly, your solution is truly elegant. How did you come up with this solution? any material or resources that you have used to get to this point? – j bel Jan 30 '22 at 12:06
  • 1
    Just practice, practice, practice! No different to any other skill. Questions like these are often asked in software engineering interviews, so there are plenty of resources out there. Always good to have a healthy mix of written materials (push through a data structures & algorithms textbook), audiovisual materials (university lectures, Grokking the coding interview, Coursera) and hands-on practice (leetcode, codechef, , hackerrank, advent of code). – Gamma032 Jan 30 '22 at 12:13
1

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!

userg
  • 46
  • 2