Lowest Common Ancestor in Binary Tree in DSA C++ - Execution Trace

Concept Flow - Lowest Common Ancestor in Binary Tree

Start at root node

↓

Check if root is null or matches p or q

Yes↓

Return root

No↓

Recurse left subtree

↓

Recurse right subtree

↓

If left and right both non-null

↓

Return root as LCA

↓

Return non-null child (left or right)

Start from root, recursively search left and right subtrees for nodes p and q. If both sides return non-null, root is LCA. Otherwise, return the non-null side.

Execution Sample

DSA C++

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  if (!root || root == p || root == q) return root;
  TreeNode* left = lowestCommonAncestor(root->left, p, q);
  TreeNode* right = lowestCommonAncestor(root->right, p, q);
  if (left && right) return root;
  return left ? left : right;
}

Finds the lowest common ancestor of nodes p and q in a binary tree by recursive search.

Execution Table

Step	Operation	Node Visited	Left Result	Right Result	Return Value	Visual State
1	Start at root	3	?	?	?	3
2	Check root == p or q	3	?	?	No	3
3	Recurse left subtree	5	?	?	?	3 -> 5
4	Check root == p or q	5	?	?	No	3 -> 5
5	Recurse left subtree	6	?	?	?	3 -> 5 -> 6
6	Check root == p or q	6	?	?	Yes (matches p)	3 -> 5 -> 6
7	Return node 6	6	6	?	6	3 -> 5 -> 6
8	Recurse right subtree	2	?	?	?	3 -> 5 -> 6, 2
9	Check root == p or q	2	?	?	No	3 -> 5 -> 6, 2
10	Recurse left subtree	7	?	?	?	3 -> 5 -> 6, 2 -> 7
11	Check root == p or q	7	?	?	Yes (matches q)	3 -> 5 -> 6, 2 -> 7
12	Return node 7	7	?	7	7	3 -> 5 -> 6, 2 -> 7
13	Recurse right subtree	4	?	?	?	3 -> 5 -> 6, 2 -> 7, 4
14	Check root == p or q	4	?	?	No	3 -> 5 -> 6, 2 -> 7, 4
15	Recurse left subtree	null	null	?	null	3 -> 5 -> 6, 2 -> 7, 4
16	Return null	null	null	?	null	3 -> 5 -> 6, 2 -> 7, 4
17	Recurse right subtree	null	?	null	null	3 -> 5 -> 6, 2 -> 7, 4
18	Return null	null	?	null	null	3 -> 5 -> 6, 2 -> 7, 4
19	Return left or right	4	null	null	null	3 -> 5 -> 6, 2 -> 7, 4
20	Return left or right	2	7	null	7	3 -> 5 -> 6, 2 -> 7
21	Return left or right	5	6	7	3	3
22	Both left and right non-null, return root	3	6	7	3	3

💡 At root 3, left subtree returned node 6, right subtree returned node 7, so root 3 is LCA.

Variable Tracker

Variable	Start	After Step 6	After Step 12	After Step 20	Final
root	3	6	7	3	3
left	?	6	6	6	6
right	?	?	7	7	7
Return Value	?	6	7	7	3

Key Moments - 3 Insights

Why do we return root immediately if root matches p or q?

Because if root is p or q, it could be the ancestor or one of the nodes itself. See step 6 where root 6 matches p and returns immediately.

Why do we return root when both left and right recursive calls are non-null?

Because it means p and q are found in different subtrees, so current root is their lowest common ancestor. See step 22 where both left=6 and right=7 are non-null, so root 3 is returned.

What if one subtree returns null?

We return the non-null subtree result because both p and q are in that subtree or one is ancestor of the other. See step 20 where left=7 and right=null returns 7.

Visual Quiz - 3 Questions

Look at the execution table at step 6, what is the return value and why?

A Returns node 6 because root matches p

B Returns null because no match

C Returns node 3 because root is ancestor

D Returns node 7 because it matches q

💡 Hint

Check step 6 in execution_table where root == p returns root

At which step does the function determine the lowest common ancestor?

A Step 12

B Step 20

C Step 22

D Step 7

💡 Hint

Look for step where both left and right are non-null and root is returned

If node q was not in the tree, how would the return value at step 22 change?

A It would return node 6

B It would return null

C It would return node 3

D It would return node 7

💡 Hint

If one subtree returns null, return the other subtree's result as per step 20

Concept Snapshot

Lowest Common Ancestor (LCA) finds the deepest node that is ancestor of both p and q.
Use recursion: if root is null or matches p/q, return root.
Recurse left and right subtrees.
If both sides return non-null, root is LCA.
Else return the non-null side.
This works for any binary tree, not just BST.

Full Transcript

The Lowest Common Ancestor in a binary tree is found by starting at the root and recursively searching for nodes p and q in the left and right subtrees. If the current root is null or matches either p or q, it returns the root immediately. Otherwise, it searches left and right subtrees. If both recursive calls return non-null, it means p and q are found in different subtrees, so the current root is their lowest common ancestor. If only one side returns non-null, that side is returned upwards. This process continues until the LCA is found or the search ends. The execution table traces each step visiting nodes, checking conditions, and returning values, showing how the recursion unfolds and combines results to find the LCA.