Finding a Local Minimum in a Complete Binary Tree with Log(N) Probes

[Jairo Rojas]

Homework Statement

Consider a complete binary tree T with n nodes (n = 2^d − 1 for some d). Each node v of T is labeled with a distinct real number x. Define a node v of T to be a local minimum if the label x is less than the label y for all nodes m that are joined to v by an edge. You are given such a complete binary tree T, but the labeling is only specified in the following implicit way: for each node v, you can determine the value x by probing the node. Show how to find a local minimum of T using only O(log n) probes to the nodes of T.

Homework Equations

The Attempt at a Solution

The way how I attempted to do this problem was by recursively finding the local minimum in the left and right subtree and then compare those 2 with the root.

int T(Root)
{
    int small_left;
    int small_right;
        if(root!=null)
           if(root->left==null)
             {
             return root->data;
             }
    small_left=T(root->left)
    small_right=T(root->right)
    if(root->data<small_left && root ->data<small_right)
        return root->data
    else if(small_left<small_right)
      return small_left;
    else
   return small_right;
}

 

[mfb]

Same problem as in the other thread, you go through the whole tree which needs O(n).