LeetCode 236 - Lowest Common Ancestor of a Binary Tree

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to find the Lowest Common Ancestor, usually abbreviated as LCA, of two nodes in a binary tree.

A binary tree consists of nodes where each node may have a left child and a right child. We are given three inputs:

root, which is the root node of the binary tree
p, one target node in the tree
q, another target node in the tree

The goal is to return the node that is the lowest node in the tree that has both p and q as descendants.

A node is considered a descendant of itself. This detail is very important because it means one of the target nodes can itself be the LCA.

For example, if node 5 contains node 4 somewhere in its subtree, then the LCA of 5 and 4 is 5.

The constraints tell us several important things about the problem:

The tree can contain up to 10^5 nodes, which means inefficient repeated traversals can become expensive.
Node values are unique, so every node can be identified unambiguously.
Both p and q are guaranteed to exist in the tree.
p != q, so we never need to handle identical target nodes.

The input is given as actual node references, not just values. This means comparisons should be done using node identity rather than searching by value.

Several edge cases are important:

One node may be an ancestor of the other.
The LCA may be the root node.
The tree may be highly unbalanced, effectively behaving like a linked list.
The two nodes may exist in completely different subtrees.
The tree may contain only two nodes.

A naive implementation can easily fail when one node is itself the ancestor of the other, especially if it only searches for split points without considering self-descendant behavior.

Approaches

Brute Force Approach

A straightforward approach is to repeatedly determine ancestor relationships.

One way to do this is:

Build a parent map for every node using DFS or BFS.
Start from node p and store all its ancestors in a set.
Move upward from node q until we find the first ancestor that also belongs to p's ancestor set.

This works because the first shared ancestor encountered while moving upward from q must be the lowest common ancestor.

Although this approach is correct, it requires additional storage for the parent map and ancestor set. It also requires traversing the tree once to construct parent relationships before solving the actual query.

Optimal Recursive DFS Approach

The key insight is that the binary tree structure itself naturally supports recursive reasoning.

At any node, there are only three possibilities:

Both target nodes are in the left subtree.
Both target nodes are in the right subtree.
One target node is in each subtree.

The third case immediately tells us the current node is the LCA.

We can use postorder DFS traversal to propagate information upward from children to parents.

The recursive function returns:

None if neither target exists in the subtree
p if subtree contains p
q if subtree contains q
The LCA node if already determined

This allows the algorithm to identify the first node where both targets appear in different branches.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Builds parent pointers and ancestor sets
Optimal	O(n)	O(h)	Single DFS traversal, uses recursion stack only

Here, n is the number of nodes and h is the height of the tree.

Algorithm Walkthrough

Start a recursive DFS traversal from the root node.

The recursion explores the tree bottom-up. This is important because we need information from child subtrees before deciding whether the current node is the LCA. 2. Define the base cases.

If the current node is None, return None because the subtree contains neither target.

If the current node equals p or q, return the current node immediately. This means we found one of the targets. 3. Recursively search the left subtree.

Store the result in a variable such as left_result.

This variable tells us whether the left subtree contains either target node or already contains the LCA. 4. Recursively search the right subtree.

Store the result in right_result.

Now we know what exists in both subtrees. 5. Determine whether the current node is the LCA.

If both left_result and right_result are non-null, then one target was found in each subtree.

That means the current node is the lowest node connecting both targets, so return the current node. 6. Propagate non-null results upward.

If only one side returned a node, return that node upward.

This propagates information about discovered targets or previously found LCAs toward the root. 7. Continue until recursion completes.

The final returned node from the root call is the LCA.

Why it works

The recursive function maintains an important invariant:

A subtree returns a non-null value if and only if it contains either p, q, or their LCA.

When both left and right subtrees return non-null values, the current node is the first point where the paths to p and q diverge. Because DFS processes children before parents, this node must be the lowest common ancestor.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from typing import Optional

class Solution:
    def lowestCommonAncestor(
        self,
        root: 'TreeNode',
        p: 'TreeNode',
        q: 'TreeNode'
    ) -> 'TreeNode':

        if root is None:
            return None

        if root == p or root == q:
            return root

        left_result = self.lowestCommonAncestor(root.left, p, q)
        right_result = self.lowestCommonAncestor(root.right, p, q)

        if left_result and right_result:
            return root

        return left_result if left_result else right_result

The implementation directly mirrors the recursive algorithm.

The first base case handles empty subtrees. If the current node is None, the subtree contains neither target.

The second base case checks whether the current node is one of the target nodes. This is critical because a node is considered its own descendant.

The recursion then searches both subtrees independently. The returned values carry information upward about whether a target node or LCA has already been found.

The condition:

if left_result and right_result:

identifies the exact moment when one target exists in each subtree. At that point, the current node is the LCA.

Finally, if only one subtree returned a non-null value, that value is propagated upward unchanged.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}

	if root == p || root == q {
		return root
	}

	leftResult := lowestCommonAncestor(root.Left, p, q)
	rightResult := lowestCommonAncestor(root.Right, p, q)

	if leftResult != nil && rightResult != nil {
		return root
	}

	if leftResult != nil {
		return leftResult
	}

	return rightResult
}

The Go implementation follows the same recursive logic as the Python version.

The main difference is the use of nil instead of None.

Pointer comparison in Go works naturally for tree nodes, so root == p and root == q correctly compare node identity.

Because Go does not support implicit truthiness checks like Python, explicit nil comparisons are required.

Worked Examples

Example 1

Input:

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

Tree structure:

The algorithm proceeds as follows:

Current Node	Left Result	Right Result	Return Value
5	5	None	5
1	1	None	1
3	5	1	3

At node 3, both left and right subtrees return non-null values. Therefore, 3 is the LCA.

Example 2

Input:

p = 5
q = 4

Traversal:

Current Node	Left Result	Right Result	Return Value
4	None	None	4
2	None	4	4
5	5	4	5

At node 5, the left subtree identifies node 5 itself while the right subtree contains node 4.

Therefore, node 5 is the LCA.

Example 3

Input:

root = [1,2]
p = 1
q = 2

Tree:

   1
  /
 2

Traversal:

Current Node	Left Result	Right Result	Return Value
2	None	None	2
1	2	None	1

Node 1 is itself one of the targets and also an ancestor of 2, so it is the LCA.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited once
Space	O(h)	Recursive call stack height equals tree height

The algorithm performs a single DFS traversal across the tree.

Each node is processed exactly once, so the total runtime is linear in the number of nodes.

The space complexity comes from recursion depth. In a balanced tree, height is O(log n). In the worst case of a completely skewed tree, recursion depth becomes O(n).

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if root is None:
            return None

        if root == p or root == q:
            return root

        left_result = self.lowestCommonAncestor(root.left, p, q)
        right_result = self.lowestCommonAncestor(root.right, p, q)

        if left_result and right_result:
            return root

        return left_result if left_result else right_result

# Build main example tree
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.right.left = TreeNode(0)
root.right.right = TreeNode(8)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)

solution = Solution()

# Example 1
assert solution.lowestCommonAncestor(
    root,
    root.left,
    root.right
).val == 3  # nodes in different subtrees

# Example 2
assert solution.lowestCommonAncestor(
    root,
    root.left,
    root.left.right.right
).val == 5  # one node is ancestor of the other

# Example 3
small_root = TreeNode(1)
small_root.left = TreeNode(2)

assert solution.lowestCommonAncestor(
    small_root,
    small_root,
    small_root.left
).val == 1  # root is LCA

# Deep left subtree
chain = TreeNode(1)
chain.left = TreeNode(2)
chain.left.left = TreeNode(3)
chain.left.left.left = TreeNode(4)

assert solution.lowestCommonAncestor(
    chain,
    chain.left.left,
    chain.left.left.left
).val == 3  # skewed tree

# LCA in middle subtree
assert solution.lowestCommonAncestor(
    root,
    root.left.right.left,
    root.left.right.right
).val == 2  # sibling nodes under same parent

# Root as LCA
assert solution.lowestCommonAncestor(
    root,
    root.left.left,
    root.right.right
).val == 3  # root connects both sides

Test Case Summary

Test	Why
Nodes in different subtrees	Validates standard LCA behavior
One node is ancestor of another	Ensures self-descendant rule works
Root and child only	Tests smallest valid tree
Skewed tree	Verifies behavior in unbalanced trees
Sibling nodes	Confirms local subtree LCA detection
Root as LCA	Ensures global ancestor detection

Edge Cases

One important edge case occurs when one target node is the ancestor of the other. Many incorrect solutions continue searching deeper and fail to recognize that a node can be its own descendant. This implementation handles the case correctly because it immediately returns when encountering either p or q.

Another important edge case is a highly unbalanced tree. A skewed tree behaves almost like a linked list, which can expose flaws in recursive traversal logic. Since this solution only depends on DFS traversal and not on balanced structure assumptions, it still works correctly.

A third edge case occurs when the LCA is the root itself. This happens when the two target nodes exist in completely different subtrees of the root. The algorithm naturally detects this because both recursive calls from the root return non-null values.

A final subtle case is when the targets are direct siblings. In this situation, their parent should be identified immediately as the LCA. The recursive returns from both child nodes cause the parent node to satisfy the condition where both left and right results are non-null.