1. Concept library
  2. Data Structures & Algorithms
  3. Module 9: Trees

Concept

Lowest common ancestor

The lowest common ancestor of two nodes is the deepest node that has both as descendants. In a BST it is the first node between the two values; in a general tree a single postorder pass finds it.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

  1. Explain what the lowest common ancestor is and why a node can be its own ancestor
  2. Find the LCA in a BST using the ordering
  3. Write the postorder solution for a general binary tree

In practice

A few lines that show Lowest common ancestor doing its job.

Python
def lca(root, p, q):
    if root is None or root is p or root is q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root          # p and q are on different sides
    return left or right

def lca_bst(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

The common mistake

Watch for

Forgetting that a node is its own ancestor. If p is an ancestor of q, the answer is p itself, which the "stop at p or q" base case handles and a stricter version misses.

What to know first

Your roadmap puts these before Lowest common ancestor, unless you already know them.

How it stays learned

Once a session shows you understand Lowest common ancestor, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

  1. Day 3First recall, while it is fresh
  2. Day 7Second, a week on
  3. Day 18Last, when it has settled
Previous in the module← Binary search trees