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

Attribution: this seems to be Problem 6 in Chapter 5 "Divide and Conquer" from the book "Algorithm Design" by Jon Kleinberg and Eva Tardos.

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

1 Answer 1

As the tree is finite and the labels are real numbers, we are assured that there is a least element in the set of labels (this question from math.SE has a proof of this simple property). In this case as all the labels are distinct, it is okay that we require the local minima to be strictly less than their neighbours. If they were, then we would have to relax this condition to "less or equal to", otherwise there may not be a solution. Nonetheless we know that there is at least one local minimum to find.

If the tree is rooted (i.e. we have a notion of a parent-child relation) we can solve the problem marginally cheaper. If the tree is unrooted, then asymptotically we can do as well, but we will likely perform more actual probes.

First we'll deal with the rooted case.

As the tree is a (complete) binary tree, each vertex has at most three neighbours, its parent and two siblings (with the root of course having no parent), so a vertex is a local minimum if its label is less than the labels of its two children and parent. Hence we can determine if a vertex is a local minimum or not with at most four probes (in fact as we will traverse the tree in an ordered fashion, we will need at most three in the rooted case).

To actually find a local minimum, we can traverse the tree, starting with the root as the current vertex, in the following fashion:

  1. Probe the current vertex's label, and the labels of its two children.
  2. If the current label is the smallest, halt and report that the current vertex is a local minimum.
  3. Else set the current vertex to the child with the smallest label, and return to step 1.

As we start from the root, we never need to worry about the parent's label - the root has no parent, and if our current vertex has a parent, then we must have discounted it in the previous iteration. Note that in step 2 it's not strictly required that we choose the smallest label, any that is smaller than the current is sufficient1, picking the smallest just gives a definite choice (again because we have distinct labels).

As we select one vertex out of the two children, our traversal picks out a path from the root to (at furthest) a leaf, thus as we have a binary tree of depth $d < \log n + 1 $ (as it's a complete binary tree with $n = 2^{d}-1$ vertices), we perform at most $3d \in O(\log n)$ probes.

In the unrooted case, we don't have such a convenient starting point, however we still have the tree structure (even if the algorithm doesn't know it). We can use the following algorithm:

  1. Pick any vertex to be the initial current vertex.
  2. Probe the label of the current vertex and all of its neighbours.
  3. If the current vertex has the lowest label, halt and report it as a local minimum.
  4. Else, select the neighbour with the lowest label as the new current vertex and return to step 2.

At each iteration we only perform at most 4 probes, so the question is how many iterations can there be? The key is to observe that we can never backtrack (we know that were we came from had a bigger label), so we must follow a simple path in the graph, but as the graph is actually a complete binary tree, the longest simple path has length $2d$. Thus even in the unrooted case we perform at most $8d \in O(\log n)$ probes.

For correctness we look at the second algorithm (the rooted case is clearly just a special case of the unrooted).

The fact that the algorithm can never backtrack also guarantees termination, as the graph is finite. Now we need only demonstrate that the vertex $v$ we terminate at is in fact a local minimum. Assume for contradiction that it is not, then it has some neighbour $u$ that has a label with a lower value. We have three cases: (1) $u$ is the previous vertex in the path which the algorithm has followed, in which case when the algorithm was at $u$, it would not have selected $v$ as the next vertex; (2) $u$ is appears in the path, but more than one iteration earlier, in this case the graph is not a tree; and (3) $u$ is not in the path the algorithm followed, but then the algorithm would select $u$ as the next vertex in step 4, and the algorithm would not have terminated at $v$. Thus $v$ must be a local minimum.

Another way to see this is to simply observe that the sequence of labels of the vertices selected by the algorithm is monotonically decreasing. From this both the termination and correctness follows immediately.

Footnote:

  1. The property that allows this is that every subtree has a local minimum - again, every finite set which has a total ordering has a least element. Thus by induction, when we extend the subtree with a new root and a sibling-subtree, we have three cases: (1) the new root is smaller than both its children, so the algorithm would terminate the new root; (2) the new root is smaller than one child but not the other, then the algorithm will not choose the larger root and must take the smallest by definition; or (3) both children are smaller, but in this case, as noted, each subtree has at least one local minimum, so we may select either.
share|improve this answer
    
A correctness proof of your algorithm is desirable: Why can we safely throw away the other sub-tree and only select the child with the smallest label? IMO, it is necessary to prove that your algorithm will find some local minimum as long as they do exist. Furthermore, a stronger property may be true: Every complete binary tree has at least one local minimum. –  hengxin Oct 25 at 2:10
    
@hengxin (hopefully) clarified. –  Luke Mathieson Oct 25 at 3:07

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.