Lowest common ancestor of a binary tree: how to find it

In this article

1. Before you start
2. Why interviewers ask this
3. Lowest common ancestor from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one problem in the coding interviews learning path.

Why interviewers ask this

The LCA problem checks whether you can solve a tree question with recursion that trusts its sub-calls, and whether you can say what changes when the tree has more structure. A candidate who writes the one-pass recursion and then notices that a binary search tree (BST) allows a much shorter walk shows the pattern of improving a solution by using a property of the input.

The question is short: given two nodes in a tree, return the deepest node that is an ancestor of both. A weak answer finds both root paths and compares them, which works but stores whole paths. A strong answer needs no extra storage beyond the recursion, names the case where one node is the ancestor of the other, and says what the answer is if a node is missing. Interview forms include the binary tree, the binary search tree, a tree with parent pointers and a company hierarchy, which is the same problem on a many-children tree.

Lowest common ancestor from first principles

Binary search tree (BST)

A binary search tree (BST) is a binary tree in which every key in a node's left subtree is smaller than the node's key and every key in its right subtree is larger, so each comparison discards one side of the tree.

Parent pointer

A parent pointer is a link from a tree node up to the node that holds it as a child, which lets a program climb from any node toward the root without searching.

Tree height

The height of a tree is the number of edges on the longest path from the root down to a leaf, and it bounds how many steps any walk from the root can take.

In plain words

Think of a family tree. Two cousins share many ancestors. The lowest common ancestor is the closest one to them: the first shared grandparent. The analogy breaks in one place. A node counts as an ancestor of itself, so the LCA of a person and their own grandchild is the person.

Stated precisely, the LCA of nodes v and w is the lowest, meaning deepest, node that has both v and w as descendants, with each node counting as a descendant of itself (Wikipedia, read October 2026). The general method for a binary tree is one traversal. It asks each subtree whether it holds a target. The LCA is the first node that hears yes from both sides.

Step 1: Return at the first target, even if the other is below it

The base case of the recursion has two parts: an empty tree returns nothing, and a node that is one of the targets returns itself immediately, without searching below it. This early return is valid when both nodes are known to exist, which is the usual interview statement; the missing-node version below changes it. The second part is what handles the case where one target is an ancestor of the other.

If the targets are B and I, and I sits below B, the search reaches B first and returns B. That is correct, because B is the lowest node that has both B and I as descendants. A candidate who keeps searching below a match would find I and then have to decide again, which is both slower and more error-prone. The cost of this step is one check per node. You now know that every call either returns a target, returns nothing or has two sub-answers to combine.

Step 2: Ask the left subtree and the right subtree

If the current node is not a target, it calls the same function on its left child and on its right child, then waits for both answers. Each answer is either a node, meaning that subtree contains at least one target, or nothing, meaning it contains neither. The recursion trusts these answers without looking inside the subtrees, which is why the code is short.

On the example tree with root A, children B and C, B's children D and E, C's children F and G, and E's children H and I, a search for D and I from the root asks B and C. The answer from C is nothing; the work inside B decides the result. This step uses recursion, so memory use grows with the height of the tree, which GeeksforGeeks gives as space proportional to the height (GeeksforGeeks, updated September 2026).

Step 3: If both sides answered, this node is the LCA

When the left call and the right call both return a node, the two targets lie on different sides of the current node, so the current node is the first place their paths meet. The function returns the current node. In the example, B asks D and E: D returns itself, E asks H and I, finds I, and returns I. B now has two answers, D from the left and I from the right, and returns B, which is the LCA of D and I.¹ The test is a single condition, left and right both non-empty. You now know where the answer comes from: the lowest node that hears from both sides.

Step 4: If only one side answered, pass it up

When only one side returns a node, the current node is not an LCA: either both targets are in that one subtree, and the answer is somewhere inside it, or only one target is there. The function returns whichever answer it received, or nothing if there were none. That passes the finished LCA, or a lone target, up the call chain until the root returns it.

In the trace for D and I, A receives B from its left and nothing from its right, and returns B. The recursion visits every node of the tree in this case, nine in the example, because it cannot rule out the right subtree without looking.¹ The method assumes that both targets exist in the tree, a condition GeeksforGeeks states explicitly; the follow-up on a missing node shows what changes when that assumption is dropped.

1 · A target returns itself2 · Ask both children3 · Both sides answered4 · One side answeredReplay

Step-by-step description

1. A node that is a target returns itself at once, even if the other target is below it.
2. A node that is not a target asks its left and right subtrees and waits for both answers.
3. B hears D from one side and I from the other, so B is the lowest common ancestor.
4. A hears only B from its left, so it passes B up and the root returns B.

• B now has two answers, D from the left and I from the right, and returns B, which is the LCA of D and I.
• In the trace for D and I, A receives B from its left and nothing from its right, and returns B.

Worked example

The four steps are the whole recursion, and this Python runs them on the tree above.

def lca(root, p, q):
    if root is None:
        return None
    if root.val == p or root.val == q:   # a target returns itself, even with the other below it
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:                   # targets on different sides: this node is the LCA
        return root
    return left or right                 # otherwise pass up whichever side answered

The code was run on four queries and checked against a reference that stores both root paths and takes the last shared node. All four agreed, and the two methods also agreed on 1,000 random binary trees of 2 to 15 nodes.¹ The table shows the queries.

A tree with a recorded order shortens the work. In a binary search tree, the first node whose key lies between the two targets, or equals one of them, is the LCA, because everything smaller is to the left and everything larger to the right (GeeksforGeeks, updated August 2026). On the balanced tree with keys 0 and 2 to 9 and root 5, the LCA of 2 and 4 is 3 after two steps, and the LCA of 2 and 5 is 5 after one.¹

Cost grows differently for the two methods. On balanced search trees of 15, 31, 63 and 127 nodes, the LCA of the two largest keys takes the ordered walk 3, 4, 5 and 6 steps, and the general recursion visits 13, 29, 61 and 125 nodes.¹ On a balanced tree of 127 nodes the ordered walk visits 6 nodes and the general recursion visits 125.

Text description of the diagram

• On a balanced tree of 127 nodes the ordered walk visits 6 nodes and the general recursion visits 125.
• On trees of 15, 31, 63 and 127 nodes the ordered walk visits 3, 4, 5 and 6 nodes.

Trade-offs and edge cases

The right method depends on what the tree gives you, and the choice is a short decision. If the tree is a binary search tree, walk down using the ordering: time proportional to the tree's height, and constant extra space when written as a loop (GeeksforGeeks, updated August 2026). If every node has a parent pointer, climb from both nodes and meet at the first shared node, in time proportional to the height (Wikipedia, read October 2026); the follow-up on parent pointers gives both ways to do it. Otherwise use the recursion above, which takes time proportional to the number of nodes.

Text description of the diagram

• A binary search tree uses the ordered walk in time proportional to its height.
• Any other binary tree uses one recursive traversal in time proportional to its size.

A binary search tree walk is only fast if the tree is balanced. A tree built from sorted insertions becomes a chain whose height grows with its size (n nodes, n − 1 edges), and then the ordered walk is no better than the general recursion.

Edge cases: when one node is the ancestor of the other, the ancestor is the answer; when a target is missing, the plain recursion returns the target it did find, not "nothing", so a version that must handle a missing node cannot stop at the first target. It must search the whole tree, as the first follow-up shows.¹

The same data confirm this: the query for D and an absent node returns D. For many queries on one tree, faster structures exist: Harel and Tarjan (1984) gave a linear-time structure with constant-time queries, and Bender and Farach-Colton (2000) gave a very simple algorithm that reduces LCA to a range-minimum problem (finding the smallest value in a stretch of a list) on an Euler tour (a walk that visits every edge of the tree) (Bender and Farach-Colton, 2000, with the history on Wikipedia, read October 2026). Those are beyond a typical interview but worth naming.

How to answer it in an interview

The spoken structure: base case, the combine rule, the cost, then the faster special case.

Common mistakes

1. Searching below a matched node. (wrong) "I keep going after I find a target." When both nodes are known to exist it wastes work and muddles the ancestor case. (right) Return the node as soon as it matches either target. The exception is the missing-node version, which must keep searching.
2. Using the BST shortcut on a plain binary tree. (wrong) Comparing keys with the targets when the tree is not ordered. (right) Check that the tree really is a search tree, or use the general recursion.
3. Forgetting that a node is its own descendant. (wrong) Returning the parent of the ancestor target. (right) A node that matches is its own LCA with a node below it.
4. Ignoring a missing node. (wrong) Assuming both exist. (right) State the assumption, or use the whole-tree version from the first follow-up.
5. Claiming the BST walk is always logarithmic. (wrong) "It is O(log n)." (right) It is proportional to the height, which is logarithmic only when the tree is balanced.

Follow-up questions

What if one of the two nodes is not in the tree?

Stopping at the first target fails here, even with a flag per target. A target below the other target is never visited, so on the example tree LCA(B, I) reports "not in tree" although the answer is B.¹ Safe version one counts targets after both sub-calls (post-order) and returns the first node whose subtree holds both. Safe version two runs the plain recursion and then searches the result's subtree for the other target; both are linear time and matched the root-path reference on 1,000 random trees.¹

How do you find the common ancestor when every node has a parent pointer?

Method one: climb from the first node to the root and store every ancestor in a set, then climb from the second node and stop at the first node in the set; time and space are proportional to the height. Method two: climb the deeper node until both are at the same depth, then climb both together until they meet; time is proportional to the height and extra space is constant. Both returned B for D and I on the example tree.¹

How do you find the LCA of more than two nodes, such as a group of employees?

The closest shared manager of a group is the LCA of the whole set. Run the same recursion with a set of targets, returning at any node in the set; with H, I and D the answer is B, and with H, D and G it is A.¹ Alternatively fold pairwise: the LCA of the first two, then of that result with the third, which also gave B.¹

What if the tree is not binary, such as a company hierarchy?

The recursion is the same with a loop over the children: count how many children return a node, and the current node is the LCA when at least two do. A company hierarchy of departments and sub-departments is such a tree.

What if the tree is not a binary search tree?

Use the general recursion, because the ordering shortcut depends on keys being arranged left smaller and right larger. For the sliding-window companion problem in the same path, see longest substring without repeating characters. The wider context is in the interview loop overview, machine learning coding rounds, system design and behavioral interviews.

Sources

1. Lowest common ancestor — Wikipedia (date = read date; pointer to Harel and Tarjan 1984, Bender and Farach-Colton 2000), 24 Oct 2026
2. The LCA Problem Revisited (Bender and Farach-Colton, LATIN 2000; course copy dated 16 May 2000) — MIT OpenCourseWare copy of the paper (Bender, Farach-Colton), 16 May 2000
3. Lowest common ancestor in a binary tree — GeeksforGeeks (page updated 20 September 2026), 20 Sep 2026
4. Lowest common ancestor in a binary search tree — GeeksforGeeks (page updated 1 August 2026), 1 Aug 2026