Local Minimum - Trees

Hi team,
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):
    :type root: TreeNode
    :return: int
              /          \
            5              11
           / \             / \
        1       4      12      13
       / \     / \     / \     / \
      2   3   7   8   5   6   7   9
    returns 1 or 4

By definition, a local min is a node whose value is smaller than that of any other nodes that are joined to it. Thus in your example, ‘1’, ‘4’, ‘5’, ‘6’, ‘7’, ‘9’ are all local minimums.

Once that’s clear, the problem is simple.

First we check the root and see if it’s smaller than both children. If yes, then we are done. If not, then we pick up its smaller child and recursively apply the check.

We terminate either 1) we found a node that is smaller than both of its children, or 2) we reach the bottom level (i.e. the leaves).

In case 1), the node at which we stop is the local min, because i) it’s smaller than both of its children, and ii) it’s smaller than its parent, which is the precondition of our deciding to check this node.

In case 2), we are left with two leaves (that are siblings), 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 min, as long as it’s smaller than its parent.

Following this approach, at most 2 nodes per level are being looked at, thus requiring only O(log n) checks since we know the tree is a complete binary tree.

1 Like