Is there anyone who can help me understand how this solution is possible? At this moment, I can’t possibly think of a O(log n) solution.
Suppose we have a complete binary tree T with n = (2^d) - 1 vertices. Each node has, associated with it a value which are all distinct (note: may not be a binary search tree). A vertex is a local minimum if the associated value is less than all adjacent vertices (parent and child(ren)), if any).
Show how to find a local minimum of T using only O(log n) inspections of vertex values.
class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = None def local_minimum(root): """ COMPLETE THIS FUNCTION :type root: TreeNode :return: int 9 / \ 5 11 / \ / \ 1 4 12 13 / \ / \ / \ / \ 2 3 7 8 5 6 7 9 returns 1 or 4 """