Medium

Lowest Common Ancestor of a Binary Search Tree

066

Given a BST encoded as level-order and two values p and q, return the lowest common ancestor value.

EXAMPLES

Example 1

Input
{
  "root": [
    6,
    2,
    8,
    0,
    4,
    7,
    9,
    -100000,
    -100000,
    3,
    5
  ],
  "p": 2,
  "q": 8
}

Output
6

FUNCTION SHAPE

root: intArrayp: intq: int→int

SOLUTION NOTE

BST properties enable O(h) instead of O(n). Three cases: LCA is on left, on right, or is current node. With balanced BSTs, h = O(log n).

Reveal reference solution +

pythonREFERENCE

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    def lca(root):
        if p.val < root.val and q.val < root.val:
            return lca(root.left)
        if p.val > root.val and q.val > root.val:
            return lca(root.right)
        # p,q are split in opposite subtrees (or one is root)
        return root

    return lca(root)

TimeO(h)

SpaceO(h)

Open on LeetCode ↗