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.

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.

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
1  
Where did you encounter the expression? –  saadtaame Feb 24 '13 at 22:44
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

1 Answer 1

As it stands, the definition is quite straightforward. A local minimum is simple a vertex where its label is less than the labels of all its neighbours.

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.

Of course there can be more than one local minimum (as suggested by the local part).

The fact that it's in a complete binary tree has no bearing on the definition, it's equally applicable to general graphs (or even hypergraphs, digraphs... pretty much anything where adjacency is well defined).

As an additional note, this concept of "local minimum of a binary tree" is not a common notion, and doesn't appear as a usual property of a (complete) binary tree, though it does look like it might be related to search trees, or similar.

share|improve this answer

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.