Height of an Unbalanced Binary Search Tree

Solution:  Determine the height of an unbalanced binary search tree

int treeHeight(struct node *tree) {
...
} 


Let's start out with a picture to make sure that we fully understand this problem.  Pic 1 shows a basic binary search tree of height 3 (three levels).  We could imagine it shorter or taller, but this seems to basically help us understand the problem.

Now, let's start thinking about cracking the problem.  Sometimes it helps to talk about what we would do intuitively to see if that gives us any insight.  Well, intuitively, we can look at the tree and find the lowest node, and just count up (or down to it). 


So, this suggests that the problem is equivalent to, what is the lowest node and how do we figure out that height.  So, let's think about this, how do we find the lowest node in a tree?  One thing we could do is do a tree traversal and assign every node a number for its depth.  This would work, but would require a data structure. 


Alternatively, let's think about what we know about the lowest node.  We know that it will have no descendants (as will any lowest level node).  This also doesn't seem to make the problem easier.


This is an example of when a train of thought does not bear out, as is common in interviews.  When you can't get to a solution, it's ok to tell the interviewer that you don't think a train of thought is productive and you're going to go back a step.  (Your interviewer may tell you this too)


So, let's go back to the original problem.  We know that we have a tree, and trees are usually recursive.  So, let's think about breaking the problem up.  And think about how a tree's height compares with its subtrees.


In this case, we can say that a tree's height is equal to the height of its taller child branch + 1 (for the root itself), as in pic 2.

This definition is sounding more promising, and recursive.  So, let's think about recursion and the recursive base case. We can go down the tree, and at each node, the height is 1 + the greater of its two sub-branches, until we reach the bottom.  The base case, of reaching the bottom (or a null node) is a height of zero.


This looks promising:
- If the node is null, return the height is 0
- otherwise, return 1 + the greater height of the left or right sub-branch


Coded, this looks like:
int treeHeight(struct node *tree) {
  int lh, rh;
  lh = rh = 0;


  //Recursive base case of end of a branch 
  if (tree == null) return 0;


  //Else, return 1 + the greater of the left-hand or right-hand sub-branch
  else {
    lh = treeHeight(tree->left);
    rh = treeHeight(tree->right);
  
    if (lh > rh) return (1 + lh);
    return (1 + rh);
  }
} 


Now, let's think think of a few boundary cases.  If we have a null tree initially, we return 0, so this is correct.  Now, let's try the code on the tree in pic 1:
We go down the lh side, then work up.  When lh and rh are equal at the bottom sub tree (with 3 as the sub-root), we return the rh, but could do either so this works too.
The, we work up and the sub branch with 3 is greater than the sub branch with 10, so we return 2, add  1 from the node 7, so we return 3 which is correct.


So, the algorithm works in our example and in our base case.


For algorithmic efficiency, we look at every node once, so this is O(n), which seems as fast as possible as we need to look at every node (given that this is an unbalanced tree) and any node could take us down a taller branch.  There is recursive overhead too.


This is a good example of: 1) following a false path as we did initially and knowing to stop, and 2) doing recursion which requires getting our base case and understanding of trees and sub-trees, which is important as these are common interview questions.




/* Please let me know if you have an alternative solution or find bugs.  Thanks, Noah */