---
title: "Lowest common ancestor: one recursion for a tree, one descent for a BST"
url: https://algopath.pro/blog/lowest-common-ancestor
language: en
summary: "The function returns the node it found or None, and a node with two answers is the ancestor. Python code for three variants, a traced run, node distance and the mistakes."
updated: 2026-11-13
---

# Lowest common ancestor: one recursion for a tree, one descent for a BST

**Short answer.** The lowest common ancestor of two nodes is the deepest node above both. In a plain binary tree one depth-first pass finds it in O(n). In a search tree one descent finds it in O(h). Below: the idea, Python code, a traced example, and the other variants.

 

## What is the lowest common ancestor?

 

An ancestor of a node is any node on its path from the root. A common ancestor of two nodes lies on both paths. The lowest one is the deepest, farthest from the root.

 

A node counts as its own ancestor. If p sits in the subtree of q, the answer is q.

 

The problem is called LCA. It appears on its own and as a step inside distance problems.

 

## How do you find the lowest common ancestor in a binary tree?

 

Recursion. The function returns p or q when it meets one. Otherwise it returns None. Ask the left subtree and the right subtree.

 

Both return something: p and q sit on different sides. The current node is the answer. One returns something: pass it up. Both None: return None.

 

One function, one pass, O(n) time, O(h) stack.

 

## What does one run look like?

 

Tree: root 3, left 5, right 1. Node 5 has children 6 and 2. Node 2 has children 7 and 4. Find the ancestor of 7 and 4.

 

From 3 go to 5, from 5 to 6: nothing there, None. From 5 to 2. From 2 to 7: that is p, return 7. From 2 to 4: that is q, return 4. At node 2 both are set, answer 2. It passes up to the root.

 

Find the ancestor of 5 and 4. Node 5 is p, return it at once without descending. The root's right subtree gives None. Answer 5, because 4 sits under it.

 

## How do you write it in 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 on different sides
    return left or right

def lca_bst(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root             # they split here, or one is root

def lca_with_parent(p, q):
    a, b = p, q                     # like intersecting two linked lists
    while a is not b:
        a = a.parent if a else q
        b = b.parent if b else p
    return a
```

 

The third function needs parent pointers. Two pointers climb and swap starts at the top. It is the same trick as intersecting two linked lists.

 

## How do the variants of the problem differ?

 

| Variant | Given | Method | Time |
| --- | --- | --- | --- |
| Binary tree | Root, p and q present | Recursion passing results up | O(n) |
| Binary search tree | Root, left-smaller rule | One descent | O(h) |
| Parent pointers | Only p and q | Two pointers climbing | O(h) |
| p or q may be missing | Root | Recursion plus a found counter | O(n) |
| Many queries | A million-node tree | Binary lifting, precomputed | O(log n) per query |

 

## How do you find it in a binary search tree?

 

Both values below the node: both ancestors are left, go left. Both above: go right. Otherwise the values split here, or the node equals one of them. That is the answer.

 

No recursion needed, a loop does it. Memory O(1).

 

## How do you compute the distance between two nodes?

 

The distance is depth(p) + depth(q) - 2 · depth(ancestor). Find the ancestor, compute three depths. One or two passes in total.

 

## When does a problem need the lowest common ancestor?

 

- "Lowest common ancestor", "LCA".
- "Distance between two nodes in a tree."
- "Deepest subtree containing both nodes."
- "Common manager of two employees" in an org chart.

 

## What mistakes break the solution?

 

- Comparing values instead of nodes. Two nodes can hold the same value.
- Assuming p and q are always present when the statement says otherwise.
- Recursing the full depth of a BST instead of looping.
- Building both root paths and comparing lists. Correct, but O(n) memory for nothing.

 

## How do you explain it in an interview?

 

Say: the function returns the node it found or None. A node with two non-empty answers is the ancestor. One sentence, and the logic is clear. Give O(n).

 

Asked about a BST, show the O(h) descent. Asked about parent pointers, show the two climbers.

 

Drill this pattern on the [lowest common ancestor](/patterns/tree-lca) page. Traversals live on the [tree traversal](/patterns/tree-traversal) page.

 

## FAQ

 

### What if p or q is not in the tree?

 

Count how many of them you met in a separate counter. At the end check that both were found. Otherwise return None.

 

### How do you answer a million queries fast?

 

Binary lifting. For each node, precompute its ancestor 1, 2, 4 and 8 steps up. A query then costs O(log n). Precomputation is O(n log n).

 

### Does the recursion work for a tree with many children?

 

Yes. Loop over all children instead of left and right. Count how many returned something. Two or more: the current node is the ancestor.

 

### Where does LCA show up in real systems?

 

Git merges use the merge base, the common ancestor of two commits. File systems find the shared folder of two paths. Class hierarchies find the common parent type.
