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 as LCA candidate

No↓

Recurse left subtree

↓

Recurse right subtree

↓

If both left and right return non-null

Yes↓

Current node is LCA

No↓

Return non-null child

↓

End

Start from root, check if it matches p or q or is null. Recurse left and right. If both sides find nodes, current node is LCA. Otherwise, return the found node.

Execution Sample

DSA C#

TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  if (root == null || root == p || root == q) return root;
  var left = LowestCommonAncestor(root.left, p, q);
  var right = LowestCommonAncestor(root.right, p, q);
  if (left != null && right != null) return root;
  return left ?? right;
}

This code finds the lowest common ancestor of nodes p and q in a binary tree by recursively searching left and right subtrees.

Execution Table

Step	Operation	Node Visited	Left Result	Right Result	Return Value	Tree State
1	Start at root	3	Pending	Pending	Pending	3
2	Recurse left subtree	5	Pending	Pending	Pending	3 -> 5
3	Recurse left subtree	6	null	null	6	3 -> 5 -> 6
4	Return from left subtree	6	null	null	6	3 -> 5 -> 6
5	Recurse right subtree	2	null	null	2	3 -> 5 -> 6, 2
6	Return from right subtree	2	null	null	2	3 -> 5 -> 6, 2
7	At node 5, left=6, right=2	5	6	2	5	3 -> 5 -> 6, 2
8	Recurse right subtree	1	null	null	1	3 -> 5 -> 6, 2, 1
9	Return from right subtree	1	null	null	1	3 -> 5 -> 6, 2, 1
10	At root 3, left=5, right=1	3	5	1	3	3 -> 5 -> 6, 2, 1
11	Return LCA	3	5	1	3	3 -> 5 -> 6, 2, 1
12	End	null	null	null	3	Final LCA is node 3

💡 Both left and right subtrees returned non-null at root 3, so root 3 is the LCA.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 7	After Step 10	Final
root	3	6	2	5	3	3
left	null	6	2	6	5	5
right	null	null	2	2	1	1
Return Value	null	6	2	5	3	3

Key Moments - 3 Insights

Why do we return root 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. See execution_table step 3 where node 6 matches p or q and returns immediately.

Why do we check if both left and right are non-null to decide LCA?

If both sides return non-null, it means p and q are found in different subtrees, so current node is their lowest common ancestor. See execution_table step 10 where left=5 and right=1, so root 3 is LCA.

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 execution_table step 7 where left=6 and right=2, so node 5 returns itself.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the return value and why?

A Return value is 5 because both left and right are null

B Return value is 5 because both left and right are non-null

C Return value is 6 because left is non-null and right is null

D Return value is null because no nodes found

💡 Hint

Check step 7 columns Left Result and Right Result; both are non-null, so return current node.

At which step does the recursion find the first node matching p or q?

A Step 10

B Step 6

C Step 3

D Step 1

💡 Hint

Look at step 3 where node 6 returns immediately because it matches p or q.

If the node q was in the left subtree of node 5 instead of right, how would the return value at step 10 change?

A Return value would be node 3

B Return value would be node 5

C Return value would be node 6

D Return value would be null

💡 Hint

If p and q are in different subtrees of root 3, root 3 remains LCA as in step 10.

Concept Snapshot

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

Full Transcript

The Lowest Common Ancestor algorithm starts at the root node. If the root is null or matches either p or q, it returns the root immediately as a candidate ancestor. Otherwise, it recursively searches the left and right subtrees for p and q. If both left and right 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, that side's result is returned upward. This process continues until the LCA is found or the recursion ends. The execution table shows step-by-step how nodes are visited, what results are returned, and how the final LCA is determined at the root node. Key moments clarify why immediate returns happen and why checking both sides is crucial. The visual quiz tests understanding of these steps and return values. This method works for any binary tree structure.

Practice

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

easy

A. The node that is a child of both nodes

B. The root node of the binary tree

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

D. The deepest node that is an ancestor of both 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: Identify the correct description

   Among the options, only the deepest common ancestor fits this definition.

3. Final Answer:

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

4. Quick Check:

   LCA = deepest common ancestor [OK]

Hint: LCA is the lowest node common to both paths [OK]

Common Mistakes:

• Confusing LCA with root node
• Thinking LCA is the smaller value node
• Assuming LCA is a child of both nodes

2. Which of the following is the correct C# method signature to find the LCA in a binary tree node class named TreeNode?

easy

A. public TreeNode FindLCA(TreeNode root, TreeNode p, TreeNode q)

B. public void FindLCA(TreeNode root, int p, int q)

C. private int FindLCA(int root, int p, int q)

D. public TreeNode FindLCA(int root, TreeNode p, TreeNode q)

Solution

1. Step 1: Analyze method parameters and return type

   The method should accept the root node and two nodes to find LCA for, and return a TreeNode representing the LCA.

2. Step 2: Match signature with correct types

   public TreeNode FindLCA(TreeNode root, TreeNode p, TreeNode q) correctly uses TreeNode for all nodes and returns TreeNode. Other options have incorrect parameter types or return types.

3. Final Answer:

   public TreeNode FindLCA(TreeNode root, TreeNode p, TreeNode q) -> Option A

4. Quick Check:

   Correct signature uses TreeNode parameters and return type [OK]

Hint: LCA method returns TreeNode and takes TreeNode parameters [OK]

Common Mistakes:

• Using int instead of TreeNode for nodes
• Wrong return type (void or int)
• Incorrect access modifier or parameter order

3. Given the following binary tree and code snippet, what will be the output of FindLCA(root, node5, node1).val?

    3
   / \
  5   1
 / \ / \
6  2 0  8
   / \
  7   4

// Code snippet:
TreeNode lca = FindLCA(root, node5, node1);
Console.WriteLine(lca.val);

medium

A. 5

B. 3

C. 1

D. 2

Solution

1. Step 1: Locate nodes 5 and 1 in the tree

   Node 5 is left child of root 3, node 1 is right child of root 3.

2. Step 2: Find lowest common ancestor

   The root node 3 is the lowest node that has both 5 and 1 as descendants.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   LCA(5,1) = 3 [OK]

Hint: LCA of nodes on different sides is their root ancestor [OK]

Common Mistakes:

• Choosing one of the nodes instead of their ancestor
• Confusing node values with LCA
• Ignoring tree structure

4. Identify the bug in this C# method to find LCA in a binary tree:

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

medium

A. Missing base case for leaf nodes

B. Should check if root.val equals p.val or q.val instead of node references

C. No bug, method is correct

D. Return statement should always return root

Solution

1. Step 1: Review base cases and recursive calls

   The method returns null if root is null, returns root if root matches p or q, then recursively searches left and right subtrees.

2. Step 2: Check logic for combining results

   If both left and right are non-null, root is LCA; else returns whichever subtree found a node. This is correct logic.

3. Final Answer:

   No bug, method is correct -> Option C

4. Quick Check:

   Standard LCA recursive method is correct [OK]

Hint: Check if both sides return non-null to find LCA [OK]

Common Mistakes:

• Comparing node values instead of references if nodes are unique
• Missing base case for null root
• Incorrect return logic

5. You have a binary tree where nodes may not be unique. How would you modify the LCA method to find the LCA of two nodes given only their values (int pVal, int qVal), assuming multiple nodes can have the same value?

hard

A. Use a method that finds paths from root to each node value and then compare paths to find LCA

B. Modify the method to return the first node found with matching value and use parent pointers to find LCA

C. Return the root node always since values are not unique

D. Use a hash set to store visited nodes and return the first common node visited

Solution

1. Step 1: Understand the problem with non-unique values

   Since values are not unique, we cannot rely on node references or values alone to find LCA directly.

2. Step 2: Use path comparison approach

   Find paths from root to each node value (may find multiple nodes), then compare paths to find the last common node, which is the LCA.

3. Final Answer:

   Use a method that finds paths from root to each node value and then compare paths to find LCA -> Option A

4. Quick Check:

   Path comparison works for non-unique values [OK]

Hint: Find paths for both values, then compare to find LCA [OK]

Common Mistakes:

• Assuming node references are unique
• Returning root always
• Using hash set without paths