---
title: "Lowest common ancestor"
url: https://algopath.pro/patterns/tree-lca
language: en
summary: "The lowest common ancestor is the deepest node that has both targets below it. One post-order pass over the tree finds it."
updated: 2026-08-24
---

# Lowest common ancestor

The lowest common ancestor is the deepest node that has both targets below it. One post-order pass over the tree finds it.

## How does Lowest common ancestor work?

Ask every node the same question. Does either target sit inside my subtree?

An empty node answers no. A node that is itself a target answers with itself.

Otherwise ask both children. Each one returns a node or nothing.

If both children answer with something, this node is the ancestor. The two targets split right here.

If only one answers, pass that answer straight up. The split has not happened yet.

The first node where both sides answer is the deepest one. Nothing above it can be lower.

- `at node 6: found` Looking for 6 and 2. Node 6 answers with itself.
- `at node 2: found` Node 2 also answers with itself.
- `at node 5: both sides answered` The two targets split here. Node 5 is the answer.
- `at node 3: only the left answered` The right subtree found nothing. Node 5 is passed up.
- `answer = 5` One pass over the tree. No node was visited twice.

## When should you use Lowest common ancestor?

- lowest common ancestor of two nodes
- deepest node that is an ancestor of both p and q
- each recursive call returns which target(s) it found below it
- path from root to each node then compare (alternate approach)
- binary tree or BST given, find where the two paths split

## What is Lowest common ancestor confused with?

- **Binary search tree** - In a search tree the values alone point the way. In a plain tree both subtrees must be asked.
- **Tree traversal** - That page is about the three visit orders. This uses post-order to answer one question.
- **Union-find (disjoint set)** - Tarjan's offline algorithm answers many pairs with a disjoint set. A single pair does not need it.
- **DP on trees** - DP on trees carries computed values upward. Here the thing carried up is only found or not found.

## What is the time and space complexity of Lowest common ancestor?

n nodes give O(n) for one query. Many queries want binary lifting, at O(log n) each.

## A worked example of Lowest common ancestor

### Ancestor inside a search tree

Both nodes live in a binary search tree. Find their lowest common ancestor.

A node counts as an ancestor of itself here.

The values themselves say which direction to walk.

If both targets are smaller, go left; if both are larger, go right. The first node between them is the answer.

```javascript
function lowestCommonAncestor(root, p, q) {
    let node = root;

    while (node) {
        if (p.val < node.val && q.val < node.val) {
            node = node.left;
        } else if (p.val > node.val && q.val > node.val) {
            node = node.right;
        } else {
            return node; // the values split here, or one of them is this node
        }
    }

    return null;
}
```

## Common mistakes with Lowest common ancestor

- **Searching for each node separately** Two searches plus a path comparison is far more work. One post-order pass answers it directly.
- **Forgetting a node can be its own ancestor** If one target sits above the other, it is the answer. Return the node as soon as it matches.
- **Assuming both nodes are present** If one is missing, the pass returns the other one. Check presence when absence is allowed.
- **Using the search-tree shortcut on a plain tree** Comparing values only works when the order is guaranteed. Otherwise both subtrees must be asked.

## Which interview problems use Lowest common ancestor?

- **Lowest common ancestor of a binary tree** The plain form: one post-order pass.
- **Lowest common ancestor of a BST** The values alone decide the direction.
- **LCA with parent pointers** Walk upward from both nodes and meet.
- **LCA of the deepest leaves** Carry the depth up alongside the node.
- **Distance between two nodes** Both depths minus twice the ancestor's depth.
- **Smallest subtree with all the deepest nodes** The same shape with different targets.
- **Step-by-step directions between nodes** Find the ancestor, then build both paths.

## JavaScript

```javascript
function lca(node, p, q) {
    if (!node || node === p || node === q) return node;
    const left = lca(node.left, p, q);
    const right = lca(node.right, p, q);
    if (left && right) return node; // p and q split here
    return left || right;
}
```

## Python

```python
def lca(node, p, q):
    if not node or node is p or node is q:
        return node
    left = lca(node.left, p, q)
    right = lca(node.right, p, q)
    if left and right:
        return node  # p and q split here
    return left or right
```

## PHP

```php
function lca(?TreeNode $node, TreeNode $p, TreeNode $q): ?TreeNode {
    if ($node === null || $node === $p || $node === $q) return $node;
    $left = lca($node->left, $p, $q);
    $right = lca($node->right, $p, $q);
    if ($left !== null && $right !== null) return $node; // split point
    return $left ?? $right;
}
```