Interview challenge · medium · binary-tree, recursion, dfs
Lowest Common Ancestor of a Binary Tree
El reto
El enunciado va en inglés, igual que en el vídeo.
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 4Idea: 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).
La solución
# Lowest Common Ancestor - ayotl.dev
class Node:
def __init__(self, v, l=None, r=None):
self.v, self.l, self.r = v, l, r
def lca(n, p, q):
# found p or q, or hit the bottom
if not n or n.v in (p, q):
return n
a, b = lca(n.l, p, q), lca(n.r, p, q)
# one on each side: n is the answer
if a and b:
return n
return a or b
t = Node(3,
Node(5, Node(6),
Node(2, Node(7), Node(4))),
Node(1, Node(0), Node(8)))
print(lca(t, 5, 1).v)
print(lca(t, 5, 4).v)
$ python3 lowest_common_ancestor_of_a_binary_tree.py
3
5