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;
lh = rh = MAX_NEGATIVE;
//
Check for null in case our node is empty
if (tree == null) return MAX_NEGATIVE; // or error value
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;
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);
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 */
An unordered binary tree is a very odd data structure. Can you think of an example of its use in the real world?
ReplyDeleteThank you for the comment Greg. Two thoughts on your question:
Delete1. 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.
While usage of unordered binary trees may be non-zero, "lots" is certainly an overstatement.
DeleteOften 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!
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
DeleteGood 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.
DeleteIf 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).
ReplyDeleteThis sort of bonsai has a straight trunk with the most extensive branches at the base. The branches get littler as they continue up the storage compartment so you end up with a shape rather like a triangle.see more
ReplyDeleteThanks for sharing us. Beavercreek OH
ReplyDelete