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 20, 2012

Largest value in an unordered, unablanced tree


Problem:  Write a function with determines the largest value in unordered, unbalanced binary tree.

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

Solution
It’s worth mentioning that if the tree were ordered, this would be trivial – going to the far right.  However, we don’t have it so easy.  So, let’s start by drawing out an example to make sure that we understand the problem.  Pic 1 is a good example of a binary tree which is unbalanced binary tree.


Looking at pic 1, see if you can find a way to intuit the largest element.  Nothing really helps here as the longest element is simply the element which is bigger than all ones.

With the only insight into finding the biggest value that we need to find the element larger than all others, let’s look at how we could do this.

First, it’s tempting to do something that we know how to do.  We could do a breadth first (or depth first) search – put all the elements in an array and then very quickly iterate through the array looking for the largest element.

This solution would work, and it would be O(n), as each element is inspected once, but it’s inelegant as it requires building a new data  structure.  So, let’s only come back to this if we need to.

Let’s look at the tree and look at a sub tree with only two nodes as in pic 2.  Essentially, we would return the largest of the value of the node, its left hand descendant and the right hand descendant.  We can use this build a recursive case (as trees usually do) and return the largest of: 1) the current value, 2) the largest value of the left hand sub-tree, or 3) the largest value of the right hand subtree.

The base case here is when we have a node with no descendants, as a null node has no value.
Using these insights, we can get the code as:

int largestValue(struct node * tree) {
    int rh, lh;
    lh = rh = MAX_NEGATIVE;
    // Check for null in case our node is empty
    if (tree == null) return MAX_NEGATIVE;  // or error value
    //Recursive base case -- no descendant nodes
    if (tree->left == null && tree->right == null)
        return tree->value;
    //else, return the largest of the lh, rh or value
    if (tree->left != null)
        lh = largestValue(tree->left);

    if (tree->right !=null)
        rh = largestValue(tree->right);
  
    //return rh if it's the biggest
    if (rh >= lh && rh >= tree->value)
        return rh;

    //return lh if it's the biggest
    if (lh >= rh && lh >= tree->value)
        return lh;

    //else, the current node's value is the biggest
    return tree->value;
}

Let’s now test this function on our sample tree in pic 1.  Yup, it works.  It's worth going through the exercise, but you can see that it returns 30, as desired.

Algorithmically, this function is O(n) as we examine each node once, with recursive overhead.  O(n) is probably the fastest that we can get as we need to look at each code.  There are certainly optimizations that we could do so we wouldn’t have to use MAX_NEGATIVE, which would be more if statements to make sure that we don’t de-reference a null pointer, but this doesn’t seem hard and we can certainly do the work as we have the structure of the algorithm.

This is a pretty good tree problem and illustrates why it’s always good to draw a picture, think of a simple sub-tree and try to intuit a problem, especially with trees.

/* Please let me know if you have alternative solutions or find bugs.  Thx, Noah */

6 comments:

  1. An unordered binary tree is a very odd data structure. Can you think of an example of its use in the real world?

    ReplyDelete
    Replies
    1. Thank you for the comment Greg. Two thoughts on your question:
      1. The questions are generally designed more to allow an job candidate to demonstrate skills.
      2. There are lots of potential reasons you would have a unordered binary tree, where in most cases the structure of the tree means something. For example, the tree structure could show the ages (or age at death) of all of a person's parent, grandparents, great grandparents... for as much data as is known. And, you may want to know how old your oldest preceding relative was. This algorithm would answer that question.

      Delete
    2. While usage of unordered binary trees may be non-zero, "lots" is certainly an overstatement.

      Often times atypical data structures have very special purpose. For example, a drop out stack (circular stack) is typically used for undo/redo functionality. I believe, your example is called a pedigree tree. Very interesting stuff!

      Delete
    3. Good point on the atypical data structures. One of the questions coming later this week explores a few of such data structure. I hope you enjoy! Noah

      Delete
    4. Good post! Maybe you don't have non-binary trees as often. But I can think of many cases where you have a tree, where the nodes are objects and are ordered by a certain object field. If you want to do queries on some other field in the object then you will have to search the whole tree given that the invariant does not hold for the particular case.

      Delete
  2. If nodes have references to their parents and we are given the liberty of destroying the input, it is possible to do this iteratively in O(n) with constant space and no recursion overhead- simply repeatedly check the value of and destroy the visited leaf nodes until we reach the root (and have no children remaining).

    ReplyDelete