cf.completefrontend
TREES & TRIES · CORE

Lowest common ancestor

Find the deepest node that has both of two given nodes below it (or is one of them).

Time O(n)Space O(h)6 practice problemsStep-through picture

The idea

An ancestor of a node is any node on the path from the root down to it: its parent, its parent's parent, and so on. A node counts as its own ancestor here. Two nodes always share at least one ancestor, the root.

The lowest common ancestor, or LCA, is the shared ancestor that is deepest in the tree, the one closest to both nodes. In a DOM tree, it is the smallest element that contains both elements.

A recursive walk finds it in one pass. Each call asks its subtree: "Do you contain p or q?" If the left subtree finds one and the right subtree finds the other, the current node is where their paths split, so it is the answer. If only one side finds something, that result is passed up unchanged.

An everyday example

Finding the shared grandparent at a family reunion

Two cousins want to know their closest shared relative. Each family branch reports upward: "I have one of the cousins" or "I have nobody". A person whose left family branch reports one cousin and whose right branch reports the other is the closest relative they share. If a person is one of the cousins themselves, they simply report "found one" upward.

How the example maps to the code
In the exampleIn the code
Asking each family branchlowestCommonAncestor(root.left, p, q) and the same on the right
"I have nobody"a call that returns null
"I am one of the cousins"root.val === p || root.val === q, so return root
Both branches found a cousinleft !== null && right !== null, so return root

From the slow way to lowest common ancestor

  1. The obvious way: find the path from the root to p and the path from the root to q, store both as arrays, and walk them side by side until they differ. The last shared node is the answer. That takes O(n) time, but it needs two searches and two extra arrays.
  2. Look at what each subtree could tell its parent instead. A subtree contains neither node, one of them, or both. If a node hears "I have one" from its left side and "I have one" from its right side, the two paths split exactly at that node, so it's the lowest common ancestor. No path arrays are needed, only those answers.
  3. So let each call return a node: null for "neither", the found node for "one", and the answer itself once it has been found lower down. A node that matches p or q can return itself at once: if the other target is below it, it is the answer, and if not, a higher node will meet the other target on its other side.
  4. Combining is then one line. If both sides returned something, return the current node; otherwise pass up whichever side found something. One postorder walk, each node asking its two children, is the recursive lowest common ancestor.

How it works

  1. If root is null, this subtree has neither node: return null.
  2. If root holds p or q, return root. Anything below cannot be lower and still contain this node.
  3. Ask the left subtree: left = lowestCommonAncestor(root.left, p, q).
  4. Ask the right subtree: right = lowestCommonAncestor(root.right, p, q).
  5. If both left and right are not null, p is on one side and q on the other, so root is the LCA.
  6. Otherwise return whichever side is not null, passing the found node (or the LCA found lower down) up to the parent.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function lowestCommonAncestor(root, p, q) {
  2. if (root === null) return null;
  3. if (root.val === p || root.val === q) return root;
  4. const left = lowestCommonAncestor(root.left, p, q);
  5. const right = lowestCommonAncestor(root.right, p, q);
  6. if (left !== null && right !== null) return root;
  7. return left !== null ? left : right;
  8. }

How fast it is

TimeO(n)
Extra memoryO(h)

In the worst case every node is visited once. The recursion keeps one call per level of the current path, up to the height h.

  • Best caseO(1)

    p or q is the root itself, so line 3 returns on the very first call.

  • Average caseO(n)

    In a typical tree the walk visits most nodes, because it can only skip the subtrees below a match.

  • Worst caseO(n)

    Both targets are deep leaves, or one of them is missing, so every node is visited once.

Common mistakes

  • Assuming both nodes are in the tree when they may not be. The code then returns the one it found. Check both exist first if that can happen.
  • Searching below a node that matches p to look for q. It isn't needed: if q is below p, then p is the answer anyway.
  • On a BST, searching both subtrees. Use the order rule to walk one path instead.
  • Comparing nodes by value when values repeat. Then two different nodes look the same. Use unique ids or compare node objects.

When to use it

Look for these clues in a problem:

  • The question asks for the closest shared parent, container, manager, or folder of two items.
  • You need the distance between two nodes in a tree: it goes up to their LCA and back down.
  • The tree is a search tree and you need where two values' search paths split.
  • You must decide which of two elements contains the other, or what contains both.

Check yourself

Answer each one in your head first, then open it.

Why can the code stop at a node that matches p without looking for q below it?

If q is below it, this node is the answer anyway. If q isn't below it, the parent will find q on its other side and decide.

In the trace, why does the root return 12 and not itself?

Only its left side found anything. A node returns itself only when both of its sides report a hit, or when it matches a target.

How would you get the distance between 7 and 30 in the trace tree?

Find the answer node 12. 7 is 1 edge below it and 30 is 2 edges below it, through 23, so the distance is 3 edges.

What does the function return when neither value is in the tree?

null, because no call ever matches at line 3, and every combine step passes null up.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 6 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule for what a call on a subtree returns: if the subtree holds both p and q, it returns their lowest common ancestor; if it holds exactly one, it returns that node; if it holds neither, it returns null. An empty subtree holds neither, so returning null for it is right.

Check each case at a node root. If root is p or q, then either the other target is below it, making root the answer, or it isn't, and root is the one target this subtree holds; returning root is right both ways. Otherwise, if both children return something, each side must hold exactly one target, since a side holding both would leave the other side with none, so the paths split at root. If only one side returns something, that side holds everything this subtree has, so passing its answer up is right.

The walk ends because it's a DFS with a null base case. By the rule, the call on the whole tree returns the lowest common ancestor, as long as both targets really are in the tree. If only one is, the rule says the call returns that one node, which is why the code alone can't tell "found the answer" from "found only p".

Going deeper

4 more ideas

Why the first node with a hit on both sides is the answer

Below the LCA, p and q are in different subtrees (or one of them is the LCA itself). Every ancestor above the LCA sees both nodes coming from the same side, so it never returns itself; it only passes the LCA up. So the node returned at the top is exactly the deepest shared ancestor.

The easier case: a binary search tree

In a BST you don't need to search both sides. If both values are smaller than node.val, the LCA is on the left; if both are bigger, it is on the right. The first node where they go different ways (or where one of them equals node.val) is the LCA. That costs only O(h).

Time, memory, and a caution

The walk visits each node at most once: O(n) time and O(h) stack memory. It assumes both p and q are in the tree. If one may be missing, the code returns the other node as if it were the LCA, so first check that both exist, or count how many were found.

With parent pointers

DOM nodes know their parentNode. Then you can walk up from p and store each ancestor in a set, then walk up from q until you hit a stored node. That first hit is the LCA, found in O(h) time without visiting the rest of the tree.

Work it by hand

Every step in a table, with why

Find the lowest common ancestor of 7 and 30 in an 8-node tree. The answer is not the root, so the trace shows a result being passed up.

root = [40, 12, 55, 7, 23, null, 61, null, null, 18, 30], p = 7, q = 30

StepCall onleftrightReturnsWhat happensWhy
17--7matches pThe walk goes 40, then 12, then 7. 7 equals p, so line 3 returns it without looking below it.
218nullnullnullnothing foundIn 12's right subtree, the walk reaches 23 and then 18. 18 is neither value, and both its children are null.
330--30matches q30 equals q, so it returns itself.
423null3030pass 30 upOnly the right side of 23 found something, so 23 passes 30 up unchanged.
51273012paths split here12 hears 7 from its left and 30 from its right. The paths to p and q split here, so it returns itself.
661nullnullnullnothing foundThe walk now checks the root's right side. 61 is a leaf that matches neither value.
755nullnullnullnothing found55 has no left child, and its right side found nothing.
84012null12pass 12 upThe root hears only from its left side, so it passes 12 up. A node above the answer never sees hits on both sides.

12. The walk made 8 calls on real nodes, one per node, because both targets are leaves here. If 7 had children, the walk would not have gone into them. The trace ends when the call on the root returns.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Lowest common ancestorO(n)O(h)One or a few questions on a plain tree with child pointers only.
Search tree walkO(h)O(1)The tree is a BST, so the values tell you which way to go.
Parent pointers and a setO(h)O(h)Nodes know their parents, like DOM elements, and you don't want to scan the whole tree.
Binary liftingO(log n)O(n log n)Many questions on a fixed tree; pay O(n log n) once to build the table.

Extra memory: O(h) for the recursion: one waiting call per level of the current path. A chain of n nodes needs n calls at once.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Lowest common ancestor and the other approaches, on a scale where each line up is 10 times more steps.
  • Lowest common ancestor, Search tree walk, Parent pointers and a set O(n)
  • Binary lifting O(log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Lowest common ancestor101,0001 million
Search tree walk101,0001 million
Parent pointers and a set101,0001 million
Binary lifting31020

Inputs that need care

5 tricky inputs
p and q are the same value
The first node that matches returns itself, so the answer is that node. This fits the definition, because a node counts as its own ancestor.
One target is above the other, like p = 12, q = 30 in the trace tree
The call on 12 returns at line 3 without searching below, and nothing else matches, so 12 comes back up as the answer, which is correct.
q is not in the tree
The code returns p's node as if it were the answer. If that can happen, count the matches first, or return { node, count } and trust the answer only when count is 2.
Repeated values in the tree
root.val === p matches the first copy the walk reaches, which may be the wrong node. Pass node objects and compare with root === p when values can repeat.
A very deep tree
The recursion depth equals the height. For trees that can be thousands of levels deep, use parent pointers or an explicit stack.

Variations and follow-ups

Twists interviewers add

Search tree version

In a BST, compare both values with node.val: if both are smaller, go left; if both are bigger, go right; otherwise this node is the split point. It walks one path, O(h) time, with O(1) memory as a loop.

Parent pointers

With a parent link on each node, walk up from p and put every ancestor in a set, then walk up from q until you meet one. Or lift the deeper node to the same depth and step both up together until they meet, which needs O(1) memory.

Many questions on one tree

If you'll ask thousands of these questions on the same tree, build a binary lifting table once in O(n log n), then answer each one in O(log n).

Common ancestor of many nodes

The same recursion works for a set of targets: return the node when it's in the set, and return root when two or more of its children report a hit. The result is the deepest node that contains them all.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "common ancestor", "smallest subtree containing both", "closest shared container", or "distance between two nodes", which is depth(p) + depth(q) - 2 * depth(lca).
  • Name the three possible return values before coding: null, one target, or the answer. The last two lines of the function are then easy to explain.
  • Ask whether both nodes are sure to exist and whether the tree is a BST. Each answer changes the best solution, and asking shows you know that.
  • Test by hand: two siblings, one node above the other, and two nodes on opposite sides of the root. The second case is where most wrong versions break.

Where frontend code uses it

The same idea in real UI code
  • The DOM Range API has a commonAncestorContainer property: the deepest node that contains both ends of a text selection. It is the LCA of the selection's start and end.
  • Node.compareDocumentPosition and Node.contains answer "is this node inside that one?", the building blocks for walking up to a shared ancestor.
  • To position a shared tooltip or highlight around two elements, you often need the smallest element that contains both.
  • In a file explorer, the deepest folder containing two selected files is their LCA, which is where a "move together" or "shared path" starts.

Related algorithms