How to

When solving these problems, learning by doing is much better than learning by reading. I encourage to you read only as far in the solution as you need, then trying to solve the problem. If you get stuck, try reading a little further. And of course, let me know if you find a better solution!

Monday, February 13, 2012

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 */


  1. Replies
    1. Great Article The IEEE Xplore digital library is your gateway to trusted research—journals, conferences, standards, ebooks, and educational courses—with more than 3 million articles to help you fuel imagination, build from previous research, and inspire new ideas. Node Js Projects for Final Year IEEE will pave a new way in knowledge-sharing and spreading ideas across the globe. Project Centers in Chennai for CSE Node.js Corporate Training JavaScript Training in Chennai

  2. When you use a genuine service, you will be able to provide instructions, share materials and choose the formatting style. Binary options recovery


  3. The strategy you have posted on this technology helped me to get into the next level and had lot of information in it. The angular js programming language is very popular which are most widely used.

    Dot Net Training in Chennai | Dot Net Training in anna nagar | Dot Net Training in omr | Dot Net Training in porur | Dot Net Training in tambaram | Dot Net Training in velachery

  4. I am glad to post a worthy article about the German Language Course and IELTS Coaching from KCR consultants, this may change your career growth and language skill.

  5. wonderful article contains lot of valuable information. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article.
    This article resolved my all queries.good luck an best wishes to the team members.continue posting.learn digital marketing use these following link
    Digital Marketing Course in Chennai