# What is the local minimum of a complete binary tree

I have this confusion. What is the 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 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
Where did you encounter the expression? –  saadtaame Feb 24 '13 at 22:44
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
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
You're talking about "the" local minimum, but there could be several ones. –  Yuval Filmus Feb 25 '13 at 4:26

A completely made up example might be a vertex $v$ with label $5$, with a parent with label $10$ and children with labels $7$ and $9$. Then $v$'s label is less than all its neighbours, so it is a local minimum.