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

"2" is considered as a local minimum if it has no children, if you want to find one within O(logn). Not possible to find "1" within O(logn)