title: Finding a "local minimum" in a binary tree
body: <p>Can you guys help me with some homework question I'm stuck in?</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>So say I have this in the tree:</p>
  
  <pre><code>    70
     /  \
   77    60
  </code></pre>
  
  <p>There are 3 cases:</p>
  
  <p>1) the root is smaller than both the left and the right child //then i'm done</p>
  
  <p>2) the root is smaller only than the left</p>
  
  <p>3) the root is smaller only than the right</p>
  
  <p>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.</p>
  
  <p>Problem here is, when we throw that left subtree, we could miss another local minimum down below. Here's an example:</p>
  
  <pre><code>                70
                /    \
              77      60
            /   \    /   \
           1    8    9    14
          / \  / \  / \   / \
         3   4 5 6  2 7  15 13
  </code></pre>
  
  <p>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.</p>