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

Question

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.

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 sufficient¹, 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.