Lowest common ancestor

Why it matters

The lowest common ancestor (LCA) appears wherever two things share a parent chain. In a company chart, it is the lowest manager that two employees both report to. In a file system, it is the deepest folder that contains two files. In version control, it is the most recent commit that two branches share. It is one of the most frequent tree questions in interviews, because the one-pass solution looks simple on paper but depends on a clear idea about what a recursive call returns.

This lesson works through the problem from the picture, explains the idea in plain words, and then gives you two methods: the one-pass recursion, and a method that first finds a path to each node. Comparing the two is good practice, because interviewers often ask for a second approach after the first.

The problem

In a binary tree, the lowest common ancestor of two nodes p and q is the deepest node that has both p and q somewhere in its subtree. A node counts as its own descendant. So if p sits above q, then p itself is the answer.

Here is an example tree. It has distinct values, which keeps the examples simple:

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

The example tree with node 2 highlighted as the lowest common ancestor of 7 and 4

Three questions about this tree:

• The LCA of 5 and 1 is 3. Node 5 is on the left of 3, and node 1 is on the right. Only 3 sits above both.
• The LCA of 5 and 4 is 5. Node 4 is below node 5, so node 5 is an ancestor of itself and of 4. It is the lowest such node.
• The LCA of 7 and 4 is 2. Both 7 and 4 are below node 2, and no node below 2 contains both.

Think of two employees, Alice and Bob, who both report up a chain of managers. The LCA is the first manager who sits above both of them. If Alice is a manager of Bob, the answer is Alice. If they are in different departments, the answer is the head of the department that contains both.

The idea: ask each subtree what it contains

Recurse into the tree and ask one question at each node: "Does this subtree contain p or q?" The recursive function returns the answer for each subtree in one of three ways:

• It returns nullptr if neither p nor q is in the subtree.
• It returns p or q if it found one of them and the other is not below it.
• It returns the LCA itself, when it has found both below this node.

The rule that makes it work is this. If a node gets a non-null answer from its left subtree and another non-null answer from its right subtree, then p and q are in different subtrees. So the current node is the lowest one that holds both. It is the LCA.

If only one side returns something, pass that result up. Either the other target was found below, or the answer is already inside that side.

Here is the code. It is the same code that the earlier version of this lesson showed, with the reasoning written as comments.

TreeNode* lca(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;   // empty, or found one target
    TreeNode* l = lca(root->left, p, q);
    TreeNode* r = lca(root->right, p, q);
    if (l && r) return root;     // p and q are on different sides: this node is the LCA
    return l ? l : r;            // only one side found something: pass it up
}

Read the first line carefully. It has two jobs. If root is null, the subtree is empty, so return null. If root is p or q, the function stops right there and returns the node. It does not search below that node, because it has already found one target. This is why the answer to "LCA of 5 and 4" is 5: the call on node 5 returns at once, because node 5 is p.

The function compares pointers, not values. Two nodes can hold the same number in a tree, so comparing pointers is safer. For this example the values are distinct, and the program below finds the nodes by value first, so both methods agree.

Worked example: the trace

Trace lca(3, 7, 4) on the example tree. Here root is the node 3, and the targets are 7 and 4. The table lists each call, what it found below, and what it returns. An empty row means the call returned at once.

The final answer is 2, as expected. The row for node 2 is the important one. Node 7 is in its left subtree, and node 4 is in its right subtree, so node 2 is the first node where the two targets meet.

Notice how the calls for nodes 0, 8 and 1 are wasted work. The search cannot know in advance that they hold nothing useful, so it looks anyway. That is the cost of this method. The search always visits every node in the worst case, which is O(n) time.

The visualizer above shows the frames of a recursive call going down and coming back up. Watch for the moment a frame has two answers from its children. That is the moment the recursion finds the LCA. The LCA function works the same way: each frame waits for both children to report before it decides what to return.

The program: input from the box

The next program reads the tree and the two values from the Input box. It has two lines. The first line is the tree in the usual level-order format. The second line holds the two values to find.

Type these two lines into the Input box:

3 5 1 6 2 0 8 -1 -1 7 4
7 4

The program uses getline to read the first line, so it can build the tree, and then cin to read the two values from the second line. It finds the nodes for the two values by a search, and then calls lca.

lca of 7 and 4 is 2

The program trusts that both values are in the tree. If one is missing, findNode returns null, the lca call returns null, and the line ans->val dereferences a null pointer. Lesson 1 showed what that crash looks like. In a production program, you would check for null first, and print a message instead.

Change the second line to 5 4 and run again. The output is lca of 5 and 4 is 5, because node 5 is an ancestor of 4.

The second method: compare two paths

The one-pass recursion is elegant, but it is easy to get wrong in an interview, because the return values carry several meanings. A second method is simpler to explain: find the path from the root down to p, and the path from the root down to q. Both paths start at the root. The LCA is the last node that appears in both paths at the same position.

Finding a path is a small backtracking search. Walk down, pushing each node onto a list. If you reach the target, the list is the path. If you do not, pop the node off the list before you return, so that the list is clean for the next branch. This push and pop pattern is the same idea you saw with the stack in the traversal lesson.

bool findPath(TreeNode* n, int target, vector<TreeNode*>& path) {
    if (!n) return false;
    path.push_back(n);                       // choose this node
    if (n->val == target) return true;       // the path ends here
    if (findPath(n->left, target, path) || findPath(n->right, target, path)) return true;
    path.pop_back();                         // undo the choice: this branch failed
    return false;
}

Once you have two paths, walk them together. While the nodes match, move on. The last matching node is the LCA.

TreeNode* lcaByPaths(TreeNode* root, int p, int q) {
    vector<TreeNode*> pathP, pathQ;
    if (!findPath(root, p, pathP) || !findPath(root, q, pathQ)) return nullptr;
    TreeNode* ans = nullptr;
    for (size_t i = 0; i < pathP.size() && i < pathQ.size(); i++) {
        if (pathP[i] != pathQ[i]) break;
        ans = pathP[i];
    }
    return ans;
}

For the example tree, the path to 7 is 3, 5, 2, 7, and the path to 4 is 3, 5, 2, 4. They agree on 3, 5 and 2, and then they split. The last agreeing node is 2.

The next program prints both paths and the LCA. It is useful for seeing the answer step by step. Type the same two lines as before into the Input box.

path to 7: 3 5 2 7
path to 4: 3 5 2 4
lca: 2

Notice that the output of this program uses the path lists, and that the LCA is found by reading two lists together. The method is O(n) time, because it walks down to each target once. Its extra space is O(h) for each path, plus the recursion stack.

Distance between two nodes

A natural follow-up question asks for the number of edges between two nodes. The answer uses the LCA. The path from p to q goes up from p to the LCA, and then down to q. So the number of edges is the depth of p minus the depth of the LCA, plus the depth of q minus the depth of the LCA. That is depth(p) + depth(q) - 2 * depth(lca).

For 7 and 4, the depths are 3 and 3, and the LCA 2 has depth 2. So the distance is 3 + 3 - 2 * 2, which is 2. The path is 7, 2, 4, which has two edges.

The next program uses the path method for the same input, and prints the distance. The depth of a node is the number of edges from the root, which is one less than the number of nodes on its path.

distance 7 to 4: 2

The variable common counts the nodes the two paths share, starting from the root. The last shared node sits at index common - 1, and that index is its depth, because the root is at index 0. So depthLca is common - 1, which is 2 for this example. The formula then gives the distance.

Checking the LCA for many queries

Interviewers sometimes ask how to answer many LCA questions on the same tree. The one-pass method rebuilds the search every time, so for many queries a better design is to prepare the depths and the ancestors once. That idea goes beyond this lesson, but you can see the start of it in the program below. It reads one tree and then a list of pairs, and it answers each pair by the path method.

Type these lines into the Input box. The first line is the tree, and each of the next lines is one query.

3 5 1 6 2 0 8 -1 -1 7 4
5 1
5 4
7 4
6 8

3
5
2
3

The four queries give 3, 5, 2 and 3. The pair 6 and 8 is in different halves of the tree, one under 5 and one under 1, so their LCA is 3. The program prints -1 when a value is not in the tree, which is a simple way to report a missing node without crashing.

Worked example: an LCA on a skewed tree

Trust the recursion more after you have traced it on a tree whose shape is simple. Take the chain that leans left, 1 2 -1 3 -1 4, which you met in the traversal lesson. The tree is 1, then 2 below it, then 3 below 2, then 4 below 3. Find the LCA of 3 and 4 by calling lca(1, 3, 4).

The call on 1 is not a target, so it asks its children. It calls lca(2), and lca(null) for the missing right child, which returns null at once. The call on 2 is not a target either, so it asks its children too. Its left child is 3, and the call lca(3) finds that its own node is p, so it returns 3 at once. It does not search below 3, and it never looks at 4. Back in the call on 2, the right side returned null, so the code returns the left answer, which is 3. Back in the call on 1, the left answer is 3 and the right answer is null, so it returns 3.

The output of the recursive program for this input is lca of 3 and 4 is 3. The trace shows the key detail: the search stopped at 3, which is the first target it met. Because 3 is an ancestor of 4, the answer is 3 itself, and the call on 3 had no reason to look further down.

Now reverse the query, asking for the LCA of 4 and 1. The call on 1 is a target, so it returns 1 immediately, without searching its children. Its answer is 1, because 1 is above 4. Each time one of the two values is an ancestor of the other, the first target on the path down is the answer, and the search ends there.

Why the one-pass recursion is correct

The recursion is short, but its correctness is not obvious, so here is the argument in plain words. Claim: for any node n, the call lca(n, p, q) returns the following value.

• If neither p nor q is in the subtree of n, it returns null.
• If exactly one of them is in the subtree of n, it returns that one.
• If both are in the subtree of n, it returns their lowest common ancestor, which lies in that subtree.

Prove the claim by looking at the three cases in the code, and assume the claim is true for the children. If n is null, the first case applies, and the code returns null. If n is p or q, the other target must be somewhere in the subtree of n, or it is outside the subtree. If it is inside, n is the answer, because it is the lowest node containing both, and the code returns it at once. If it is outside, the code returns n, which is the one target in the subtree, matching the second case.

Otherwise, n is neither target. If both targets are in the same child's subtree, that child returns their LCA, and the other child returns null. Then l && r is false, and the code returns l, which is the right answer. If the targets are in different child subtrees, each child returns one target, so l && r is true, and n is the lowest node containing both. The code returns n, which is correct. Finally, if only one target is below n, one child returns it and the other returns null, and the code passes the single answer up, which is the second case of the claim.

This argument shows why the order of the checks matters. The check for null and for a target must come first. Without it, a target that sits above another target would not stop the search, and the answer would be the wrong, lower node.

Edge cases in depth

• The same value twice, p equal to q. The call on the node p returns that node at once, because root == p is true. The LCA of a node with itself is the node. In the path program, the two paths are identical, so every node on the path is shared, and the last one is the answer. Test it with the tree 1 2 3 and the query 2 2, whose answer is 2.
• One value above the other. If p is an ancestor of q, the answer is p, because the call on p returns before it reaches q. The query 1 2 on the tree 1 2 3 gives 1.
• The root is the LCA. When the two targets are in different subtrees of the root, the root is returned, and the query 2 3 on 1 2 3 gives 1.
• A missing value. The recursion does not fail on its own. A value that is not in the tree is never matched, so every call on the way down returns null, and the top call returns null. The program must check for that. The path program in this lesson prints -1 for a missing node, and the query 5 5 on 1 2 3 shows it.
• An empty tree. The top call receives null and returns null at once, so the answer is null for every query. A program that reads ->val from that null answer crashes, which is why the check matters.
• A deep tree. The recursion is as deep as the tree, so a chain of a million nodes risks a stack overflow. For such a tree, use the parent-pointer method below, or an iterative walk.

Comparing the approaches

Each approach has a different cost profile, and an interviewer may ask you to compare them. The table gives the usual costs, with n nodes and height h.

For the parent-pointer method, mark every ancestor of p, including p, in a set. Then climb from q one parent at a time, and the first node that is marked is the answer. Each climb takes O(h) steps, and the set holds at most h nodes.

The binary search tree shortcut is a preview of the next module. There, every node holds a value that is bigger than everything on its left and smaller than everything on its right. So you can decide which way to go from the values alone: if both targets are smaller than the current node, go left, if both are bigger, go right, and otherwise the current node is the answer. That walk visits one path, not the whole tree. The plain binary tree in this module has no such rule, so the full walk is needed.

Variations you will meet

• LCA of many nodes. Fold the pairwise method, as the practice exercise shows. The LCA of a list is the LCA of the first two, combined with the third, and so on. Each step returns a node that is then used as the new target.
• No LCA. If the two values are in different trees, or one is missing, the answer is null. Say so, and print a clear message instead of crashing.
• Distance between two nodes. Use the formula from the lesson, which needs only the depths of the two targets and their LCA.
• Is one node an ancestor of another. The answer is yes exactly when the LCA equals the first node. That is one line of code once you have the LCA.
• Count the nodes between two nodes. A path with d edges has d + 1 nodes, and d - 1 of them lie strictly between the two ends. Say whether the question wants the ends counted, because the answer changes by two.

What happens inside the recursion

The recursion explores the tree in postorder: it asks both children before it decides about the node. Each call holds its two child answers in local variables, which live on the call stack. Those answers exist only until the call returns, so there is no need for a global table of results. The stack depth is the height of the tree, and each frame holds two pointers and the parameters.

A plain binary tree gives no hint about which side holds a target, so the search cannot skip a branch. It must look at both sides of each node until it has found both targets or has finished the tree. In the worst case, that is every node. This is why the method is O(n), and why the binary search tree version, which can skip one side at each node, is faster.

A trace of the path method on the example tree

The path method has one idea that the recursion does not: when a branch fails, the code removes the node it added. Trace findPath for the query 6 and 8 on the example tree, to see that step.

Searching for 6 starts at the root 3 and goes left to 5, then left to 6. The node 6 matches, so the path is 3, 5, 6, and the search stops there.

Searching for 8 is longer. The search goes to 3, then to 5, then to 6. Node 6 does not match, and its children are missing, so the code removes 6 from the path and returns false. Back in 5, the right side goes to 2. Node 2 has the children 7 and 4, and neither matches, so both are removed as their branches fail, and then 2 is removed. Node 5 has no more branches, so it is removed too. Back at 3, the search goes right to 1. Node 1 tries its left child 0, which fails, and removes it. Then it tries 8, which matches. The path is 3, 1, 8.

Compare the two paths. Both begin with 3, so 3 is shared. At the next position, 5 is on one path and 1 is on the other, so they differ. The last shared node is 3, which is the LCA. The trace shows that the path lists hold only the current route at each moment, because every failed branch was removed. Without that step, the list would fill up with nodes from dead ends, and the paths would be wrong.

Designing the answer on a whiteboard

Interviewers often watch you reason on a board, so use a fixed order. First, say the definition in your own words: the lowest node that has both values in its subtree, where a node counts as its own descendant. Second, draw a small tree with the two values, and find the answer by eye. Third, pick the method, and say why. The recursion is short and needs no extra space beyond the stack. The paths are easier to explain. Fourth, write the base cases first, before the recursive case, because they are the safe part and they make the rest of the code easy to read. Fifth, trace your code on the small tree you drew. Sixth, state the cost: O(n) time and O(h) space for either method, and say that a missing value must be handled.

This order keeps the answer clear even when you make a small slip. The interviewer can see that you know the definition, have a check on a small case, and understand the cost, and those three points are worth more than a perfect first draft.

Common mistakes and their real messages

Passing values where pointers are expected

The LCA function takes TreeNode* arguments, not integers. If you pass 7 and 4 directly, the compiler says:

error: invalid conversion from 'int' to 'TreeNode*' [-fpermissive]

The fix is to find the nodes first, with a helper such as findNode, and then pass their pointers.

Forgetting that a node is its own descendant

The rule that the first line of lca returns root when root is p or q is essential. Without it, the LCA of 5 and 4 would search below 5, find 4 on one side and nothing on the other, and return 4. The correct answer is 5, because a node counts as its own ancestor.

Using the value comparison from the binary search tree lesson

The shortcut for binary search trees compares values with the current node, and goes left or right. That shortcut does not work on a plain binary tree, because there is no order between the left and right children. The recursive method in this lesson does not depend on order, which is why it works here.

Comparing values when values repeat

If the tree has two nodes with the same value, comparing values can pick the wrong one. Compare pointers when you have them, and compare values only when the problem guarantees they are unique. The programs above assume unique values, and they say so in the input format.

Dereferencing a missing node

If one of the values is not in the tree, findNode returns null, the LCA is null, and ans->val crashes with exit status 139. The fix is to check for null before you read the answer. The path-based program in this lesson prints -1 for a missing value instead.

Debugging walkthrough

Suppose your lca returns 5 for the input 7 4, but the correct answer is 2. Work through this sequence.

First, write the expected answer and the path to each target on paper. For 7 the path is 3, 5, 2, 7, and for 4 it is 3, 5, 2, 4. The LCA is 2, because that is the last node the two paths share.

Second, add a print at the top of lca: cout << "visit " << (root ? root->val : -1) << "\n";. Run the program and read the order of visits. Check the first node where l && r should be true. If the answer is 5, the code returned at node 5. That means 5 saw a non-null answer from only one side, or it returned early.

Third, check the early return. If the first line is if (!root || root == p) return root; and it forgets root == q, then the call at node 7 would not stop properly, and the result changes. Check each part of the condition.

Fourth, test the smallest case that exposes the bug. The tree 1 2 with the query 1 2 should give 1, because 1 is the parent of 2 and counts as its own ancestor. If your code gives 2, the check for root == p is missing or in the wrong place.

Interview questions you should be ready for

• How do you find the LCA in a binary tree in one pass? Recurse. Return null for an empty subtree, return the node if it is one of the targets, and return the node itself when both children return non-null answers.
• What is the time and space cost? O(n) time, because each node may be visited once. O(h) space for the recursion. Both are the same for the path method, plus the space for the two paths.
• What if one of the nodes is not in the tree? The one-pass method returns null, unless you count how many targets you find. The path method returns null when a path is not found.
• How does the binary search tree version differ? It compares values and goes one way, so it visits only one path from the root. It is faster, but it needs an ordered tree.
• How would you answer many queries quickly? Precompute the depth and the ancestors of each node once, then answer each query from that table. Binary lifting is the usual name for that technique.

Real-world uses

Version control systems find the merge base of two branches, which is the LCA of two commits in the commit graph. Tools that compare two files in a folder tree find the nearest common folder to decide where to start looking. A permissions system checks which role is the closest shared ancestor of two users, so that it can grant a shared right at the right level. In each case, the LCA is the answer to "where do these two things meet?"

Practice

1. Find the distance between two nodes in the example tree. Use the formula depth(p) + depth(q) - 2 * depth(lca), and check the answer for 6 and 8.

2. Write vector<TreeNode*> pathTo(TreeNode* root, int target) that returns the path from the root to the target, or an empty vector if the target is not found.

vector<TreeNode*> pathTo(TreeNode* root, int target) {
    vector<TreeNode*> path;
    findPath(root, target, path);   // leaves path empty if not found
    return path;
}

3. Write bool isAncestor(TreeNode* root, int a, int b) that returns true when node a is an ancestor of node b. A node is its own ancestor.

bool isAncestor(TreeNode* root, int a, int b) {
    TreeNode* ans = lcaByPaths(root, a, b);
    return ans && ans->val == a;
}

4. Trace lca(3, 5, 1) by hand and write down each call and its return value, in the same style as the trace table in this lesson.

5. Write a function that returns the number of nodes on the path from the root to a target, using findPath.

int pathLength(TreeNode* root, int target) {
    vector<TreeNode*> path;
    if (!findPath(root, target, path)) return 0;
    return (int)path.size();
}

6. Explain why the recursive LCA can return a node that is not one of p or q, and why that is correct.

7. Write the LCA of three nodes: lca3(root, a, b, c). Hint: the LCA of three nodes is the LCA of the first two, combined with the third.

TreeNode* lca3(TreeNode* root, TreeNode* a, TreeNode* b, TreeNode* c) {
    TreeNode* ab = lca(root, a, b);
    return lca(root, ab, c);
}

8. Predict the output of the path-based program when the Input box holds the tree 1 2 3 and the query 2 3. Then run it.

9. Find the LCA of a node and itself. Explain what the one-pass method returns, and why.

10. Two-step question. A perfect tree has height 3 (four levels). What is the largest possible distance between two of its nodes, and which two nodes achieve it?

What you now know

• The lowest common ancestor is the deepest node that has both targets in its subtree. A node counts as its own descendant.
• The one-pass recursion returns null for an empty subtree, returns a target when it finds one, and returns the current node when both children return non-null answers.
• The path method finds the path from the root to each target, then reads the two paths together to find the last shared node.
• The distance between two nodes is depth(p) + depth(q) - 2 * depth(lca).
• Both methods take O(n) time, and O(h) space.
• A missing node returns null, so check for it before you read the answer.
• The plain binary tree has no ordering rule, so the search must check both sides.