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

• Jairo Rojas
In summary: So, the solution is to only go through the left or right subtree. This can be done by comparing the root with its left and right child and recursively going to the subtree with the smaller value. This way, the number of probes needed is reduced to O(log n).In summary, the problem is to find a local minimum in a complete binary tree with n nodes, where each node is labeled with a distinct real number. This can be done by recursively comparing the root with its left and right subtree and going to the subtree with the smaller value, resulting in O(log n) probes to the nodes.
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.

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:
Same problem as in the other thread, you go through the whole tree which needs O(n).

What is a complete binary tree?

A complete binary tree is a type of binary tree where every level, except possibly the last, is completely filled with nodes, and all nodes are as far left as possible.

How many probes are required to find a local minimum in a complete binary tree?

In a complete binary tree with N nodes, it takes log(N) probes to find a local minimum. This is because the tree can be divided into two equal subtrees at each level, reducing the search space by half with each probe.

What is a local minimum in a binary tree?

A local minimum in a binary tree is a node that is smaller than its immediate neighbors. However, it may not be the smallest value in the entire tree.

What is the best approach for finding a local minimum in a complete binary tree?

The best approach is to start at the root node and compare it to its two children. If the root is smaller than both children, it is a local minimum. Otherwise, move to the smaller child and repeat the process until a local minimum is found.

Can a complete binary tree have more than one local minimum?

Yes, it is possible for a complete binary tree to have more than one local minimum. This can occur if there are multiple nodes that are smaller than their immediate neighbors.

• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Engineering and Comp Sci Homework Help
Replies
2
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
3
Views
1K
• Engineering and Comp Sci Homework Help
Replies
2
Views
2K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
2
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Programming and Computer Science
Replies
3
Views
3K