Question

need algorithm not code otherwise will downvote 10 times use ms team or latex code or pdf only
Consider an n-node complete binary tree T, where n = 2d − 1 for some d. Each node v of T is labeled with a real number xv. You may assume that the real numbers labeling the nodes are all distinct. A node v of T is a local minimum if the label xv is less than the label xw for all nodes w that are joined to v by an edge.
You are given such a complete binary tree T, but the labeling is only specified in the following implicit way: for each node v, you can determine the value of xv by probing the node v. Show how to find a local minimum of T using only O(logn) probes to the nodes of T.
Note:- dont use handwritten image

Answer 1

/*Dear Student, As you requested for the only algorithm, I have spent a lot of time and made these statements with algorithms in a simple and clear manner, so if you got something from it, then give it an Upvote. Thank You.*/

Q) Local minimum of T using only O(logn) probes to the nodes of T.

Ans: The algorithm is the following.

• We begin at the root of the tree. and see if r is smaller than its two children. If so, the root is the local minimum. Otherwise, we move to any smaller child and iterate
• The algorithm terminates when either (1) we reach a node v that is smaller than both its children or (2) we reach a leaf w. In the former case, we return v; in the latter case, we return w.

To find the local minimum in T we evaluate localMin(r). The algorithm performs O(d) =O(log n) probes of the tree;

We must now argue that the returned value is a local minimum. If the root is returned it is a local minimum as explained above.

• If we terminate in case (1) v is a local minimum because v is smaller than its parent (since it was chosen in the previous iteration) and its two children (since we terminated).
• If we terminate in case (2),w is a local minimum because w is smaller than its parent (again since it was chosen in the previous iteration).

Algorithm: Local Minimum in tree T

LocalMin(v) //This function finds the local minimum in the subtree rooted at v in T.