GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 40

Answer 1

The algorithm is as follows:

1. Let $v$ be the root.
2. If $v$ is a local minimum, output $v$.
3. Otherwise, update $v$ to be a child that has a smaller value, and go to step (b).

Since, the algorithm moves to a child in each step, the running time is at most the depth of the tree, which is $O(\log n)$.

Comments

what if there is no local minimu then I have to check for each node right?

---

@shadymeee They have given that node values are distinct and its a tree so obviously there will always exist atleast one node which will be the local minimum. The worst case would be when it is the leaf node, that's why the time complexity is O(Logn).

Answer 2

$Answer : O(logn)$

Hint : A leaf node is considered as local minimum if its value is less than its parent node.

Answer 3

Please find the explanation below.

Hope, this helps.

Comments

what if 1 is in the right subtree in place of 8, then how to find the local min in log n time? 

---

See we don't need to find all the possible local minimum the above logic will find atleast one local minimum.

Since all the labels are distinct it is pretty sure that in one of paths from root to leaf their exist a local minimum. In short we don't care what other minimums are.

You may have a question also that what if leaf itself not local minimum so we need to check other paths also ?

See the above case will never happen because we are going down only when it is lesser than parent so in worst case leaf node will definitely be local minimum.

---

thanks./