# Homework Help: Another log(n) algorithm

1. Apr 3, 2016

### Jairo Rojas

1. The problem statement, all variables and given/known data
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.

2. Relevant equations

3. 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.
Code (Text):

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;
}

Last edited: Apr 3, 2016
2. Apr 4, 2016

### Staff: Mentor

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