AI Hints
Home›DSA in Python Tutorial›Tree Practice
DSA in Python · Lesson 69 of 132

Practice: Lowest Common Ancestor

Where two paths meet.

⏱ 2 min read▶ Video at 1:21:10🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Practice: Lowest Common Ancestor
From the video: Practice: Lowest Common Ancestor
  • 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.

lca.pypython
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))
Output
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.

keyvalue
Both smallergo left
Both biggergo right
They splitfound it
CostO(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
Next up: Heaps — the smallest always on top