Card 04/ 08
Tree Patterns Example: The Lowest Common Ancestor of Two Nodes
Each call reports whether it found either node below it, and the first call to hear yes from both sides is the ancestor.
The lowest common ancestor of two nodes is found in one pass by having each call return what it found below it, and letting the first call that hears from both sides return itself. The lowest common ancestor of two nodes is the deepest node that has both of them in its subtree, where a node counts as being in its own subtree. The tree has root 8, with children 3 and 7; 3 has children 6 and 1, and 1 has children 9 and 4; 7 has a right child, 2. It is not a binary search tree, so the values give no hint of which way to go.
What is the lowest common ancestor of 1 and 4?
1 itself. 4 sits below 1, and 1 is in its own subtree, so 1 is the deepest node that holds both.
Each call returns one of three things: nothing, when neither node is in its subtree; the node it found, when one is; or itself, when its left call and its right call both found one. A call on a node that is itself one of the two returns at once without looking below, which covers the case in the reveal: if the other node is underneath, no call above will hear from a second side, and the found node travels up as the answer. The notes give what each call returns for 6 and 4.
8, hears 3 from the left only, returns 3
3, hears 6 and 4 from both sides, returns itself
6, is one of the two, returns 6
1, hears 4 from the right, returns 4
9, returns nothing
4, is one of the two, returns 4
7, returns nothing
null, empty left child
2, returns nothing
The listing finds the ancestor of four pairs, including the reveal's.
class Node:
def __init__(self, value: int, left: Node | None = None, right: Node | None = None) -> None:
self.value = value
self.left = left
self.right = right
def lowest_common_ancestor(node: Node | None, a: int, b: int) -> Node | None:
if node is None or node.value in (a, b):
return node
left = lowest_common_ancestor(node.left, a, b)
right = lowest_common_ancestor(node.right, a, b)
if left is not None and right is not None:
return node
return left if left is not None else right
tree = Node(8, Node(3, Node(6), Node(1, Node(9), Node(4))), Node(7, None, Node(2)))
for a, b in [(9, 4), (6, 4), (1, 4), (9, 2)]:
ancestor = lowest_common_ancestor(tree, a, b)
print(f"{a} and {b}: {ancestor.value if ancestor else None}")9 and 4: 1
6 and 4: 3
1 and 4: 1
9 and 2: 8The method assumes both nodes are in the tree: if only 6 were, the root would return 6 and call it the ancestor. Each node is visited at most once, so the search is O(n) time and O(h) space. A binary search tree allows a shortcut, walking down from the root towards whichever side holds both values in O(h), which the Binary Search Trees topic in Data Structures covers; this version needs no ordering at all.
← → move through sections and cards