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