Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Leetcode 236. Lowest Common Ancestor of a Binary Tree

Given a binary tree and two nodes p and q, find their lowest common ancestor — the deepest node that has both p and q as descendants (a node can be a descendant of itself). The tree can be large (up to 2e5 nodes), nodes are unique and p and q are guaranteed to exist.

Asked at:

DESCRIPTION

Input:

root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

Output:

Explanation: The LCA of nodes 5 and 1 is 3, as it's the deepest node that has both as descendants

Constraints:

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

Understanding the Problem

Let's understand what we're being asked to do. We have a binary tree and two nodes p and q somewhere in that tree. We need to find their lowest common ancestor (LCA) - the deepest node that has both p and q as descendants.

Important: a node can be a descendant of itself. This means if p is an ancestor of q, then p itself is the LCA!

Let's trace through an example tree:

If p=5 and q=1, the LCA is 3 (the root is the lowest node that has both as descendants).

If p=5 and q=4, the LCA is 5 (node 5 is an ancestor of node 4, and a node can be its own descendant).

Key constraints: Both p and q are guaranteed to exist in the tree, all node values are unique, and the tree can have up to 200,000 nodes.

Edge cases to consider: What if p or q is the root? What if one node is a direct ancestor of the other? What if the tree has only two nodes?

Building Intuition

The LCA is the split point where the paths from root to p and root to q diverge.

If we're at a node and p is in the left subtree while q is in the right subtree (or vice versa), then this current node must be the LCA. If both are in the same subtree, the LCA must be deeper in that subtree.

This observation means we can solve this with a single tree traversal. At each node, we ask: 'Are p and q in different subtrees of this node?'

If yes, we've found the LCA. If no, we recurse into whichever subtree contains both nodes. We don't need to store paths or do multiple passes!

Think of the tree as a family tree. The LCA is the most recent common ancestor.

Imagine tracing the lineage from each person back to their ancestors. The LCA is the first ancestor they share when going backwards. If person A is an ancestor of person B, then A is their own LCA (since A is in the lineage from A to root, and also in the lineage from B to root).

We can find this by exploring the tree and checking: 'At this ancestor, do the two people branch off in different directions, or are they both down the same branch?'

Common Mistakes

Forgetting that a node can be its own descendant - this causes incorrect handling when one target is an ancestor of the other

Not handling the base case properly - forgetting to return the node when it matches p or q breaks the algorithm

Confusing the return value semantics - the function returns the LCA if both nodes are found, or the single found node if only one is in the subtree

Trying to use level-order traversal (BFS) - this problem requires bottom-up information flow, which is natural with DFS but awkward with BFS

Attempting to store paths and compare them - this uses extra space and multiple passes when a single DFS traversal suffices

Optimal Solution

Use recursive DFS to traverse the tree. At each node, recursively search for p and q in the left and right subtrees. If the current node is p or q, return it. If both left and right recursive calls return non-null values, it means p and q are in different subtrees, so the current node is the LCA. If only one side returns non-null, propagate that result upward (both nodes are in that subtree). This finds the LCA in a single traversal.

Visualization

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def lowest_common_ancestor(root, p, q):
    """
    Find the lowest common ancestor of two nodes in a binary tree.
    Uses recursive DFS to search for p and q in subtrees.
    """
    # Base case: if root is None or root is one of the target nodes
    if root is None:
        return None
    
    if root.val == p or root.val == q:
        return root
    
    # Recursively search in left and right subtrees
    left_result = lowest_common_ancestor(root.left, p, q)
    right_result = lowest_common_ancestor(root.right, p, q)
    
    # If both left and right return non-null, current node is LCA
    if left_result is not None and right_result is not None:
        return root
    
    # Otherwise, return the non-null result (both nodes in same subtree)
    if left_result is not None:
        return left_result
    else:
        return right_result

Start finding LCA of p and q

0 / 41

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We visit each node in the tree exactly once during the DFS traversal, where n is the number of nodes

Space Complexity: O(h) The recursion stack can go as deep as the height of the tree. In the worst case (skewed tree), this is O(n). In a balanced tree, this is O(log n)

What We've Learned

Recursive post-order traversal for LCA: The LCA problem is solved elegantly using post-order traversal (left-right-root) because you need information from both subtrees before making a decision at the current node - if both subtrees return non-null, the current node is the LCA.
Null propagation as signal mechanism: Use null returns to propagate search results up the tree - return the found node (p or q) when discovered, return null when neither is found, and this creates a natural signaling system where the first node receiving two non-null children is the answer.
Self-ancestor handling: A critical insight is that a node can be its own ancestor - if you find p and q is in p's subtree (or vice versa), then p itself is the LCA, which the algorithm handles naturally by returning p immediately when found.
Single-pass efficiency through bottom-up processing: This solution achieves O(n) time with O(h) space by visiting each node exactly once and making the LCA decision during the return phase, avoiding the need for separate path-finding or parent-pointer approaches that would require multiple passes.
Common mistake - premature decision making: A frequent error is trying to determine the LCA while traversing down (top-down), but you lack the information needed until you've explored both subtrees - always gather information from children before processing the parent in tree ancestry problems.
Pattern extension to organizational hierarchies: This LCA algorithm directly applies to finding common managers in org charts, nearest common ancestors in file systems, or merge points in version control - any hierarchical structure where you need to find the closest common parent of two entities.

Test Your Understanding

Why is tree the right data structure for this problem?

tree provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid December, 2025

Junior

Mid December, 2025

Atlassian

Staff

Late November, 2025

Senior

Get Premium to View All 50+ Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More