LeetCode · #236

Lowest Common Ancestor of a Binary Tree Solution

Use post-order DFS to detect where the search paths for p and q first meet.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #236

🏗️

Pattern

Tree DFS — post-order merge

Given the root of a binary tree and two nodes p and q, return their lowest common ancestor — the deepest node that has both as descendants, where a node can be a descendant of itself.

Example

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

Section Two · Brute Force

Store Parent Pointers

Traverse once to record each node's parent, then walk upward from one node while marking ancestors, and finally climb from the other until you hit a marked one.

Problem: This works, but it needs extra hash maps/sets. A recursive DFS can solve the problem directly with the tree structure alone.

Section Three · Optimal

Recursive DFS — O(n)

At each node, ask the left and right subtrees whether they contain p or q.

💡 Mental model: Imagine searching for two people in a building. If one is found in the left wing and the other in the right wing, the current hallway intersection is their first common meeting point — the LCA.

Core logic

If the current node is null, return null.
If the current node equals p or q, return it.
Recurse into left and right.
If both sides return non-null, current node is the LCA.
Otherwise return whichever side is non-null.

Why this works: The first node where the search results come back from both sides is exactly the deepest split point between p and q.

Section Four · Trace

Visual Walkthrough

When both recursive calls succeed, current node is the answer

Section Five · Implementation

Code — Java & Python

Java — post-order DFS

 class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) return root;
return left != null ? left : right;
    }
}

Python — post-order DFS

 class Solution:
def lowestCommonAncestor(self, root, p, q):
if not root or root == p or root == q:
return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left if left else right

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
Parent map + ancestor set	O(n)	O(n)
Recursive DFS	O(n)	O(h)

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Why it matters
One node is ancestor of the other	That ancestor is the LCA, and the base case handles it naturally.
Targets on different sides of root	The root becomes the answer.
Skewed tree	Still correct, but recursion depth becomes O(n).

⚠ Common Mistake: Assuming LCA works like the BST version. In a general binary tree, there is no ordering rule like “go left if both are smaller.” You must search both subtrees.

← Back to Trees problems

LearningTree

LC 236 · Lowest Common Ancestor of a Binary Tree — Solution & Explanation | DSA Guide