MediumDepth-First SearchTreeUpdated Sep 2026

236. Lowest Common Ancestor of a Binary Tree

Asked at Google, Meta, Amazon, Microsoft and 4 more

Difficulty

Medium

Time

O(n)

Space

O(h)

Pattern

Depth-First Search

Companies

8

Problem

You are given the root of a binary tree and two nodes in it, p and q. Return the lowest common ancestor (LCA) of p and q.

The LCA is the deepest node in the tree that has both p and q in its subtree. A node counts as a descendant of itself, so if p is an ancestor of q, then p is the answer.

All node values are unique, p and q are different nodes, and both are guaranteed to exist in the tree. Return the node itself (the whole node), not just its value.

Find the deepest shared ancestor

65p = 57243answer01q = 185 lives in the left subtree of 3 and 1 lives in the right subtree, so 3 is theLCA.
For p = 5 and q = 1, the deepest node whose subtree holds both of them is node 3.

Constraints

  • ●The number of nodes is in the range [2, 10^5].
  • ●-10^9 <= Node.val <= 10^9
  • ●All Node.val are unique.
  • ●p != q
  • ●p and q will exist in the tree.

Examples

Example 1
Inputroot = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output3
WhyNode 5 sits in the left subtree of 3, and node 1 sits in the right subtree. Their paths split right at the root, so 3 is the deepest node that contains both.
Example 2
Inputroot = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output5
WhyNode 4 is inside the subtree of node 5, so 5 is an ancestor of 4. Since a node may be its own descendant, 5 itself is the lowest common ancestor.
Example 3
Inputroot = [1,2], p = 1, q = 2
Output1
WhyThe root 1 is the parent of 2, so 1 is the deepest node that has both nodes below it.

Asked At

8 companies
CompanyDifficulty
GoogleMediumView all Google questions →
MetaMediumView all Meta questions →
AmazonMediumView all Amazon questions →
MicrosoftMediumView all Microsoft questions →
AppleMediumView all Apple questions →
NetflixMediumView all Netflix questions →
UberMediumView all Uber questions →
AtlassianMediumView all Atlassian questions →

How to Think About It

1

Recursive approach: if the current node is null, p, or q, return it. These are the base cases.

2

Recurse on left and right children. If both return non-null, the current node is the LCA (p and q are in different subtrees).

3

If only one side returns non-null, that side contains both nodes (or one of them). Pass that result up.

4

If neither returns non-null, neither subtree contains p or q. Return null.

5

Why it works: the recursion naturally finds the deepest node where p and q's paths diverge. That's the LCA.

6

Edge cases: p is ancestor of q (p is LCA), q is ancestor of p (q is LCA), same node (that node is LCA).

Optimal Approach

Step 1: Base case — if root is null, or root equals p or q, return root.
Step 2: Recurse: left = lca(root.left, p, q), right = lca(root.right, p, q).
Step 3: If both left and right are non-null, current node is LCA → return root.
Step 4: Return the non-null one (or null if both are null).

Time: O(n) — visit every node in worst case. Space: O(h) — recursion stack.

Post-order recursion returns the answer upward

65returns 5724301returns 18The left child of 3 returns 5 and the right child returns 1.657243both sides non-null → return 3018Because both subtrees reported a hit, the current node 3 is the LCA and isreturned to the caller.if root is null, p or q → return rootleft = recurse(left), right = recurse(right)if left and right → return rootelse return left or right
Each call returns p, q, or the LCA found so far; the first node that gets a non-null answer from both sides is the LCA.
ComplexityTime O(n)Space O(h)In the worst case every node is visited once, and h is the tree height for the recursion stack.

What Trips People Up in Real Interviews

1

Confusing this with LCA of a BST. In a BST, you can use the BST property to narrow the search. In a general binary tree, you can't.

2

Not handling the case where one node is the ancestor of the other. If p is an ancestor of q, p is the LCA.

3

Forgetting the base case: if the current node is null, p, or q, return it.

4

Trying to find the LCA by storing paths. That's O(n) space and more complex than the recursive approach.

5

Not handling the case where p and q are the same node. If p == q, that node is the LCA of itself. The algorithm handles this through the base case, but some candidates add unnecessary logic.

Solution Code

O(n) time
def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    return left or right

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Lowest Common Ancestor of a Binary Tree problem?

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q. The lowest common ancestor is the deepest node that has both p and q as descendants.

How do you solve Lowest Common Ancestor of a Binary Tree?

The optimal approach runs in O(n) time and O(h) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Lowest Common Ancestor of a Binary Tree?

Lowest Common Ancestor of a Binary Tree is asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Atlassian. It is a medium difficulty problem.

What are common mistakes on Lowest Common Ancestor of a Binary Tree?
  • Confusing this with LCA of a BST. In a BST, you can use the BST property to narrow the search. In a general binary tree, you can't.
  • Not handling the case where one node is the ancestor of the other. If p is an ancestor of q, p is the LCA.
  • Forgetting the base case: if the current node is `null`, p, or q, return it.
  • Trying to find the LCA by storing paths. That's `O(n)` space and more complex than the recursive approach.
  • Not handling the case where p and q are the same node. If p == q, that node is the LCA of itself. The algorithm handles this through the base case, but some candidates add unnecessary logic.