Geek Answers Handbook

Finding a "local minimum" in a binary tree

Can you guys help me with the homework question I'm stuck in?

A local minimum in a complete binary tree is defined as a node that is smaller than all its neighbors (neighbors = parent, left child, right child). I need to find a local minimum in a given complete binary tree, each of its nodes which has a different number, in O (logn) time of complication.

Well, since the requirement is O (logn), I tried to think about how to go through one path through a tree to a leaf. Or maybe I could only look at half the tree each time in recursion, and that way it would do logn.

So to speak, I have it in a tree:

70 / \ 77 60

There are 3 cases:

1) the root is smaller than the left and right child //, then I finished

2) the root is less than the left

3) the root is less than the right

The above tree is case 2. Therefore, let's “throw away” the left subtree, because there is no way that 77 could be a “local minimum”, since it is larger than its parent. So, we have the right subtree left. And so on, until we find a local minimum.

The problem is that when we drop this left subtree, we can skip the next local minimum below. Here is an example:

  70 / \ 77 60 / \ / \ 1 8 9 14 / \ / \ / \ / \ 3 4 5 6 2 7 15 13

So, in this case, the only local minimum is “1”, but we skipped it, because at first we decided to search for the correct subtree of the root.

+4
source share
3 answers

"2" is considered a local minimum if it has no children, if you want to find it inside O (logn). Unable to find "1" within O (logn)

+1
source

By definition, a local min is a node whose value is less than any other nodes that are attached to it. So in your example “1”, “5”, “6”, “2”, “7”, “13” are local minima.

Once this is clear, the problem is simple.

First, we check the root and see if it is smaller than both. If so, then we are done. If not, then we take his smaller child and recursively apply validation.

We conclude either 1) that we find a node that is smaller than both of his children, or 2) we reach the lower level (i.e. leaves).

In case 1) the node that we will stop at is a local minimum, since i) it is smaller than both its children, and ii) it is smaller than its parent, which is a prerequisite for our decision to check this node.

In case 2) we are left with two sheets (these are brothers and sisters), and at least one of them is smaller than the parent (otherwise the parent will be returned). Then either (or both) of them are local minimal if they are less than its parent.

After this approach, no more than 2 nodes per level are viewed, which requires only an O (log n) check.

Hope this is helpful and clear enough.

+7
source

I believe this can be done in O (N).

Start at the root. Check if he has a child who is smaller than him. If so, go to this child. If not, we did.

Then repeat this process, continuously selecting a child that is smaller than the current node. Check if it is a local min. If not, repeat.

By doing this, we guarantee that the current parent node is always larger than itself. If the algorithm stops, there can be only two cases:

  1. The current node is a sheet.
  2. The two children of the current node are both larger than it.

In any case, the current node is a local min.

0
source

More articles:


All Articles