Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

How to find a local minimum of a complete binary tree?

Consider an $n$-node complete binary tree $T$, where $n = 2^d − 1$ for some $d$. Each node $v \in V(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 \in V(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 each a complete binary tree $T$, but the labeling is only specified in the following implicitly 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$.

share|improve this question
3  
You gotta give us some more info to answer this. It could be anything, does the vertices/nodes represent something? Is the tree a heap, and the local minimum for a given subtree (subtree generated by some node) the least value in the subtree? –  Pål GD Feb 24 '13 at 22:42
3  
I'm not sure where the problem is, the definition you have seems pretty straightforward, a local minimum is any vertex where its label is less than the labels of all its neighbours. The complete binary tree part seems unimportant (unless your tree is embedded in a larger graph). –  Luke Mathieson Feb 25 '13 at 0:18
2  
You could just traverse the tree in any convenient order, and for each node check if its value is less than the parent/children. Other than doing that, I'm at a loss. –  vonbrand Feb 25 '13 at 1:07
3  
You're talking about "the" local minimum, but there could be several ones. –  Yuval Filmus Feb 25 '13 at 4:26
2  
There is an algorithm which will find one of the local minima in a complete binary tree in time O(log n). Is this what you're looking for? Here's a hint: call a node a "candidate local minimum" if it's less than its parent. Now, for any candidate local minimum: either it is a local minimum or it has a child which is a candidate local minimum. –  rici Feb 25 '13 at 18:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.