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

Concept Flow - Lowest Common Ancestor in Binary Tree

Start at root

↓

Check if root is null or matches p or q

↓

If yes, return root

↓

Recurse left subtree

↓

Recurse right subtree

↓

If both left and right return non-null

↓

Current node is LCA

↓

Else return non-null child

↓

End

Start from root, check base cases, recurse left and right, if both sides find nodes, current node is LCA, else return found node.

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	N/A	N/A	N/A	Tree: 3 / \ 5 1 / \ / \ 6 2 0 8 / 7 4
2	Check root == p or q?	3	N/A	N/A	No	Same as above
3	Recurse left subtree	5	N/A	N/A	N/A	Subtree rooted at 5
4	Check node 5 == p or q?	5	N/A	N/A	Yes (p)	Found p at node 5
5	Return node 5 up	5	N/A	N/A	5	Return 5 to parent call
6	Recurse right subtree	1	N/A	N/A	N/A	Subtree rooted at 1
7	Check node 1 == p or q?	1	N/A	N/A	No	Continue search
8	Recurse left subtree	0	N/A	N/A	N/A	Subtree rooted at 0
9	Check node 0 == p or q?	0	N/A	N/A	No	Continue search
10	Recurse left subtree	null	N/A	N/A	null	Reached leaf null
11	Recurse right subtree	null	N/A	N/A	null	Reached leaf null
12	Return null up from 0	0	null	null	null	No p or q found here
13	Recurse right subtree	8	N/A	N/A	N/A	Subtree rooted at 8
14	Check node 8 == p or q?	8	N/A	N/A	No	Continue search
15	Recurse left subtree	null	N/A	N/A	null	Leaf null
16	Recurse right subtree	null	N/A	N/A	null	Leaf null
17	Return null up from 8	8	null	null	null	No p or q found here
18	Return null up from 1	1	null	null	null	No p or q found in right subtree
19	At root 3, left=5, right=null	3	5	null	5	Left subtree found p, right null
20	Return 5 as LCA	3	5	null	5	LCA is node 5
21	End	N/A	N/A	N/A	5	Lowest Common Ancestor is node 5

💡 Returned node 5 as LCA because left subtree found p and right subtree returned null

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 19	Final
root	3	5 (left subtree call)	1 (right subtree call)	3 (root)	3 (root)
left	N/A	5	N/A	5	5
right	N/A	N/A	null	null	null
return	N/A	5	null	5	5

Key Moments - 3 Insights

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

Because if the current node is p or q, it could be the ancestor or one of the nodes we search for. Returning it helps identify if p or q is found in that subtree (see step 4 in execution_table).

Why do we check if both left and right recursive calls are non-null?

If both left and right return non-null, it means p and q are found in different subtrees, so current node is their lowest common ancestor (see step 19).

What if one subtree returns null?

If one subtree returns null, it means neither p nor q is found there, so we return the non-null subtree result upwards (see steps 18 and 19).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is returned when node 5 is visited?

A Null

B Node 5 (matches p)

C Node 3 (root)

D Node 1

💡 Hint

Check the 'Return Value' column at step 4 in execution_table

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

A Step 12

B Step 10

C Step 19

D Step 6

💡 Hint

Look for the step where both left and right results are non-null or the LCA is returned

If node q was in the right subtree of node 1, how would the return value at step 19 change?

A It would be node 3

B It would be node 1

C It would be null

D It would be node 5

💡 Hint

If both left and right are non-null, the current node is LCA (see explanation in key_moments)

Concept Snapshot

Lowest Common Ancestor (LCA) in Binary Tree:
- Start at root node
- If root is null or matches p or q, return root
- Recursively search left and right subtrees
- If both sides return non-null, current node is LCA
- Else return non-null child
- Returns the lowest node that is ancestor to both p and q

Full Transcript

The Lowest Common Ancestor algorithm starts at the root of the binary tree. It checks if the current node is null or matches either of the target nodes p or q. If yes, it returns that node. Otherwise, it recursively searches the left and right subtrees. If both recursive calls return non-null, it means p and q are found in different subtrees, so the current node is their lowest common ancestor. If only one side returns non-null, it returns that side upwards. This process continues until the LCA is found or the search ends. The execution table traces each step, showing nodes visited, recursive results, and return values. Key moments clarify why immediate returns happen and how the LCA is identified. The visual quiz tests understanding of these steps. The snapshot summarizes the method in simple steps.

Practice

1. What is the Lowest Common Ancestor (LCA) of two nodes in a binary tree?

easy

A. The node that appears first in an inorder traversal

B. The root node of the binary tree

C. The deepest node that is an ancestor of both nodes

D. The node with the smallest value between the two nodes

Solution

1. Step 1: Understand the definition of LCA

   The Lowest Common Ancestor is the deepest node in the tree that has both given nodes as descendants (a node can be a descendant of itself).

2. Step 2: Differentiate from other nodes

   The root node is not always the LCA unless both nodes are in different subtrees of the root. The smallest value or traversal order does not define LCA.

3. Final Answer:

   The deepest node that is an ancestor of both nodes -> Option C

4. Quick Check:

   LCA = deepest common ancestor [OK]

Hint: LCA is the deepest shared parent node [OK]

Common Mistakes:

• Confusing LCA with root node
• Choosing node based on value instead of position
• Using traversal order to find LCA

2. Which of the following is the correct base case check in a recursive function to find LCA in a binary tree?

easy

A. if (root->left == NULL) return root;

B. if (root == NULL) return NULL;

C. if (root->right == NULL) return root;

D. if (root == NULL) return root;

Solution

1. Step 1: Identify the base case for recursion

   When the current node is NULL, it means we reached the end of a path without finding the target nodes, so return NULL.

2. Step 2: Check other options

   Returning root when left or right child is NULL is incorrect because the node itself may not be the LCA. Returning root when root is NULL is invalid.

3. Final Answer:

   if (root == NULL) return NULL; -> Option B

4. Quick Check:

   Base case: root NULL returns NULL [OK]

Hint: Return NULL when node is NULL in recursion [OK]

Common Mistakes:

• Returning root instead of NULL when node is NULL
• Checking only left or right child for base case
• Returning root when root is NULL

3. Consider the following binary tree and code snippet to find LCA of nodes 5 and 1:

struct Node {
  int val;
  struct Node *left, *right;
};

struct Node* findLCA(struct Node* root, int n1, int n2) {
  if (root == NULL) return NULL;
  if (root->val == n1 || root->val == n2) return root;
  struct Node* left_lca = findLCA(root->left, n1, n2);
  struct Node* right_lca = findLCA(root->right, n1, n2);
  if (left_lca && right_lca) return root;
  return (left_lca != NULL) ? left_lca : right_lca;
}

// Tree structure:
//       3
//      / \
//     5   1
//    / \ / \
//   6  2 0  8
//     / \
//    7   4

// Call: findLCA(root, 5, 1);

What node value will the function return?

medium

A. 3

B. 5

C. 1

D. 2

Solution

1. Step 1: Trace recursive calls for nodes 5 and 1

   Starting at root (3), neither 5 nor 1 matches root. Recursively check left subtree (root 5) and right subtree (root 1). Left subtree returns node 5, right subtree returns node 1.

2. Step 2: Determine LCA based on returned nodes

   Since both left_lca and right_lca are non-NULL, the current root (3) is the LCA.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   LCA(5,1) = 3 [OK]

Hint: If both sides return nodes, current root is LCA [OK]

Common Mistakes:

• Returning one of the nodes instead of their ancestor
• Confusing node values with LCA
• Not checking both left and right subtree results

4. The following code attempts to find the LCA of two nodes in a binary tree but has a bug: <pre>struct Node* findLCA(struct Node* root, int n1, int n2) { if (root == NULL) return NULL; if (root->val == n1 || root->val == n2) return root; struct Node* left_lca = findLCA(root->left, n1, n2); struct Node* right_lca = findLCA(root->right, n1, n2); if (left_lca != NULL && right_lca != NULL) return root; else if (left_lca != NULL) return left_lca; else if (right_lca != NULL) return right_lca; return NULL; } // Bug: The function sometimes returns NULL if one of the nodes does not exist in the tree. What is the likely cause of this bug?

medium

A. The function incorrectly returns root when both children are NULL

B. The base case returns NULL instead of root

C. The function does not handle the case when n1 equals n2

D. The function does not check if both nodes exist in the tree before finding LCA

Solution

1. Step 1: Analyze the function's behavior

   The function returns NULL if it does not find either node in a subtree. If one node is missing in the tree, the function may return NULL even if the other node exists.

2. Step 2: Identify missing existence check

   The function assumes both nodes exist. Without verifying both nodes are present, it can return NULL incorrectly.

3. Final Answer:

   The function does not check if both nodes exist in the tree before finding LCA -> Option D

4. Quick Check:

   Check node existence before LCA [OK]

Hint: Verify both nodes exist before LCA search [OK]

Common Mistakes:

• Ignoring node existence check
• Assuming base case handles all scenarios
• Not handling identical nodes input

5. Given a binary tree where nodes can have duplicate values, which modification is necessary to correctly find the Lowest Common Ancestor of two nodes identified by their values?

hard

A. Modify the function to find nodes by their unique memory addresses or pointers instead of values

B. Use inorder traversal to find the first occurrence of each value

C. Return the node with the smaller value as LCA

D. Ignore duplicates and return the first matching node found

Solution

1. Step 1: Understand the problem with duplicates

   When values are not unique, identifying nodes by value alone can lead to incorrect LCA because multiple nodes share the same value.

2. Step 2: Use unique identifiers for nodes

   Using unique memory addresses or pointers ensures the function finds the exact nodes intended, avoiding confusion from duplicates.

3. Final Answer:

   Modify the function to find nodes by their unique memory addresses or pointers instead of values -> Option A

4. Quick Check:

   Use unique node references for duplicates [OK]

Hint: Use node pointers, not values, when duplicates exist [OK]

Common Mistakes:

• Assuming values are unique identifiers
• Using traversal order to pick nodes
• Ignoring duplicates causing wrong LCA