Share
Explore BrainMass

Divide and Conquer a Binary Tree

Consider an n-node complete binary tree T, where n=2^d - 1 for some d. Each node v of T is labeled with a real number x_v. You may assume that the real numbers labeling the nodes are all distinct. A node v of T is a local minimum if the label x_v is less than the label x_w for all nodes w 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_v by probing the node v. Show how to find a local minimum of T using only O(log n) probes to the nodes of T.

Solution Preview

For each node v, it has label x_v. It has a left child u and a right child w. We have the following three cases:
Case 1: x_u < x_v < x_w. Then I go to subtree rooted at u and continue to check whether u is a local minimum or not.
Case 2: x_w < x_v < x_u. Then I go to subtree rooted at w and continue to check whether w is a local minimum or not.
Case 3: x_v < x_u and x_v < x_w. Then I claim that v is a local minimum. Because v has three neighborhood nodes u, w and its parent, say p. the label of v is less than the label of u and w. From case 1 an case 2, v is obtained because its label
x_v is less than the label x_p of its parent ...

Solution Summary

This solution provides guidelines to show how to find a local minimum of a binary T.

$2.19