Interview challenge · medium · binary-tree, recursion, dfs

Lowest Common Ancestor of a Binary Tree

The challenge

Given a binary tree and two values p and q that are in it, return their lowest common ancestor: the deepest node that has both p and q in its subtree. A node counts as being in its own subtree.

Example

        3
      /   \
     5     1          LCA(5, 1)  ->  3
    / \   / \         LCA(5, 4)  ->  5
   6   2 0   8
      / \
     7   4

Idea: one recursive pass. If the current node is p or q (or empty), return it. Otherwise ask the left and right subtrees. If both answers are not empty, p and q are on different sides and this node is the answer; if only one is, pass it up. Time O(n), stack O(height).

The solution

1# Lowest Common Ancestor - ayotl.dev
2class Node:
3    def __init__(self, v, l=None, r=None):
4        self.v, self.l, self.r = v, l, r
5
6
7def lca(n, p, q):
8    # found p or q, or hit the bottom
9    if not n or n.v in (p, q):
10        return n
11    a, b = lca(n.l, p, q), lca(n.r, p, q)
12    # one on each side: n is the answer
13    if a and b:
14        return n
15    return a or b
16
17
18t = Node(3,
19         Node(5, Node(6),
20              Node(2, Node(7), Node(4))),
21         Node(1, Node(0), Node(8)))
22print(lca(t, 5, 1).v)
23print(lca(t, 5, 4).v)

$ python3 lowest_common_ancestor_of_a_binary_tree.py

The video

Watch on YouTube →