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.
How to find a local minimum of a complete binary tree?
terminology;graphs;binary trees