Finding a "local minimum" in a binary tree

Question

Can you guys help me with some homework question I'm stuck in?

A local minimum in a full binary tree is defined as a node which is smaller than all of its neighbors (neighbors = parent, left child, right child). I need to find a local minimum in a given full binary tree, which each of its nodes has a different number, in O(logn) complixity time.

Well, since the requirement is O(logn) then I tried to think of a way to go only through 1 path through the tree down to a leaf. Or maybe I could look only at a half of the tree each time in a recursion and this way it will do the logn.

So say I have this in the tree:

    70
   /  \
 77    60

There are 3 cases:

1) the root is smaller than both the left and the right child //then i'm done

2) the root is smaller only than the left

3) the root is smaller only than the right

The above tree is case 2. So let's "throw away" the left subtree because there's no way the 77 can be a "local minimum" since it's greater than its parent. So we're left with the right subtree. And so on, until we find the local minimum.

Problem here is, when we throw that left subtree, we could miss another local minimum down below. Here's an example:

                70
              /    \
            77      60
          /   \    /   \
         1    8    9    14
        / \  / \  / \   / \
       3   4 5 6  2 7  15 13

So in this case, the only local minimum is "1", but we missed it because at the beginning we decided to search through the right subtree of the root.

Answer 1

By definition, a local min is a node whose value is smaller than that of any other nodes that are joined to it. Thus in your example, '1', '5', '6', '2', '7', '13' are all local minimums.

Once that's clear, the problem is simple.

First we check the root and see if it's smaller than both children. If yes, then we are done. If not, then we pick up its smaller child and recursively apply the check.

We terminate either 1) we found a node that is smaller than both of its children, or 2) we reach the bottom level (i.e. the leaves).

In case 1), the node at which we stop is the local min, because i) it's smaller than both of its children, and ii) it's smaller than its parent, which is the precondition of our deciding to check this node.

In case 2), we are left with two leaves (that are siblings), and at least one of them is smaller than the parent (otherwise the parent will be returned). Then, either (or both) of them are local min, as long as it's smaller than its parent.

Following this approach, at most 2 nodes per level are being looked at, thus requiring only O(log n) checks.

Hope this is helpful and clear enough.