Practice: Lowest Common Ancestor
Where two paths meet.
In a family tree, the lowest common ancestor of two people is the closest relative they share. In a binary search tree, there's a lovely short way to find it. Pause, and think about where the two values split apart.

- The closest shared relative
- In a BST, it's easy
- Where do the paths split?
Follow until they split
Start at the root. If both values are smaller, the answer must be on the left. If both are bigger, it's on the right. As soon as they go different ways, or one of them is this node, we've found the lowest common ancestor. Run it.
from tree import sample
def lca(node, a, b):
while node:
if a < node.value and b < node.value:
node = node.left
elif a > node.value and b > node.value:
node = node.right
else:
return node.value
root = sample()
print(lca(root, 4, 7), lca(root, 1, 7), lca(root, 13, 10))6 3 10
Also uses tree.py
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
def sample():
return TreeNode(8,
TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
TreeNode(10, None, TreeNode(14, TreeNode(13))))
PICTURE = ' 8\n / \\\n 3 10\n / \\ \\\n 1 6 14\n / \\ /\n 4 7 13'What it shows
This uses the binary search tree rule to skip whole subtrees, so it takes O of height steps. In a plain binary tree, without the ordering rule, you'd search both sides with recursion instead, which is O of N. Knowing the structure lets you pick the faster answer.
| key | value |
|---|---|
| Both smaller | go left |
| Both bigger | go right |
| They split | found it |
| Cost | O(height) |
Summary
Follow both values down until they split. That node is the lowest common ancestor. Next, a different kind of tree. The heap.
Key takeaways- Both smaller? Left
- Both bigger? Right
- Split? Answer