Log inSign up
mediumleetcodeNot Started

Lowest Common Ancestor of a Binary Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: "The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself)."

Example 1 · Example 1: Nodes in Different Subtrees:

Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1 Tree: 3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4
Output: 3
Explanation: LCA of 5 and 1 is 3.

Example 2 · Example 2: One Node is Ancestor of Other:

Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 4 Tree: 3 / \ 5 1 / \ 6 2 / \ 7 4
Output: 5
Explanation: Node 5 is ancestor of 4, so LCA is 5.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master bottom-up postorder tree traversal.
  • Identify the bifurcation point where two targets divide.
  • Handle the case where one target node is the ancestor of the other.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Lowest common ancestor of two nodes.
  • First common fork in binary tree.
  • General binary tree (not BST).

Algorithmic Decision Tree:

  • If root == null || root == p || root == q -> return root.
  • left = lca(root.left); right = lca(root.right).
  • If left && right -> return root.
  • return left ? left : right.

Connected Patterns:

Lowest Common Ancestor of a Binary Search TreeLowest Common Ancestor of Deepest LeavesDistance Between Two Nodes in a Binary Tree

1. Root-to-Node Path Comparison

Intuition

Find root-to-node path vectors for both p and q. Compare paths index-by-index: the last node where path1[i] == path2[i] is the LCA.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Helper getPath(root, target, path).
  2. Step 2: Collect pathP and pathQ from root.
  3. Step 3: Loop i while pathP[i] == pathQ[i].
  4. Step 4: Return pathP[i - 1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 bool getPath(TreeNode* root, TreeNode* target, vector<TreeNode*>& path) {
9 if (!root) return false;
10 path.push_back(root);
11 if (root == target) return true;
12 if (getPath(root->left, target, path) || getPath(root->right, target, path)) return true;
13 path.pop_back();
14 return false;
15 }
16public:
17 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
18 vector<TreeNode*> pathP, pathQ;
19 getPath(root, p, pathP);
20 getPath(root, q, pathQ);
21 int i = 0;
22 while (i < pathP.size() && i < pathQ.size() && pathP[i] == pathQ[i]) i++;
23 return pathP[i - 1];
24 }
25};
26
27int main() {
28 // Sample driver execution
29 cout << "Execution completed successfully." << endl;
30 return 0;
31}
32

Time & Space Complexity

  • Time complexity: O(n) — Two path searches taking O(n) each; comparison takes O(h).
  • Space complexity: O(h) — Two path arrays storing up to h nodes.

2. Parent Pointer Mapping with Ancestor Set

Intuition

Map parent pointers for tree. Traverse p up to root, adding all ancestors to a set. Traverse q up to root: the first ancestor of q in p's set is the LCA.

When to apply: Iterative approach with parent pointers.

Algorithm

  1. Step 1: Map parent[child] = parent using BFS.
  2. Step 2: Collect all ancestors of p into a set.
  3. Step 3: Climb q up parent links; if q in set, return q.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
10 unordered_map<TreeNode*, TreeNode*> parent;
11 queue<TreeNode*> qu;
12 qu.push(root);
13 parent[root] = nullptr;
14 while (!parent.count(p) || !parent.count(q)) {
15 TreeNode* cur = qu.front(); qu.pop();
16 if (cur->left) { parent[cur->left] = cur; qu.push(cur->left); }
17 if (cur->right) { parent[cur->right] = cur; qu.push(cur->right); }
18 }
19 unordered_set<TreeNode*> ancestors;
20 while (p) {
21 ancestors.insert(p);
22 p = parent[p];
23 }
24 while (!ancestors.count(q)) {
25 q = parent[q];
26 }
27 return q;
28 }
29};
30
31int main() {
32 // Sample driver execution
33 cout << "Execution completed successfully." << endl;
34 return 0;
35}
36

Time & Space Complexity

  • Time complexity: O(n) — Parent mapping visits nodes in O(n); ancestor search is O(h).
  • Space complexity: O(n) — Parent map and ancestor set take O(n) space.

3. Single-Pass Postorder DFS

Intuition

Base case: if root == null || root == p || root == q return root. Recurse left and right. If both left and right return non-null, root is the LCA. Otherwise return left ? left : right.

When to apply: Optimal gold-standard solution.

Algorithm

  1. Step 1: If root == null || root == p || root == q return root.
  2. Step 2: left = lowestCommonAncestor(root.left, p, q).
  3. Step 3: right = lowestCommonAncestor(root.right, p, q).
  4. Step 4: If left != null && right != null return root.
  5. Step 5: Return left != null ? left : right.

LCA Bifurcation Trace for p = 5, q = 1

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Inspect root 3
Visual state
Values and pointers at this exact step
tree
Root
3
L (p)
5
R (q)
1

Node order shown; add connections to display explicit tree edges.

p: 5q: 1
Check / comparison
Left returns 5; Right returns 1
Decision / next transition
Both children returned non-null targets.
Why this step matters

Step 1: Inspect root 3. Recurse left: finds node 5 (returns 5). Recurse right: finds node 1 (returns 1).

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
10 if (!root || root == p || root == q) return root;
11 TreeNode* left = lowestCommonAncestor(root->left, p, q);
12 TreeNode* right = lowestCommonAncestor(root->right, p, q);
13 if (left && right) return root;
14 return left ? left : right;
15 }
16};
17
18int main() {
19 // Sample driver execution
20 cout << "Execution completed successfully." << endl;
21 return 0;
22}
23

Time & Space Complexity

  • Time complexity: O(n) — Traverses tree in single pass.
  • Space complexity: O(h) — Call stack bounded by tree height h.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Root-to-Node Path ComparisonO(n)O(h)Compare path arrays from root.Path allocation.
2.Parent Pointer Map with Ancestor SetO(n)O(n)Climb parent links into ancestor set.Map allocations.
3.Single-Pass Postorder DFSOptimalO(n)O(h)Bifurcation detection in postorder recursion.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • p is root: root is LCA.
  • p is direct ancestor of q: p is returned as LCA.
  • p and q are leaves in opposite subtrees: root is LCA.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Contrast LCA in general binary tree (O(n) DFS) with LCA in BST (O(h) value comparison).
  2. Explain why the code naturally handles the case where p is the ancestor of q without needing special branches.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does returning root when root == p || root == q correctly handle the case where p is an ancestor of q?

Back to DSA Sheet