- #1

Jairo Rojas

- 17

- 0

## 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.

Code:

```
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: