Lowest Common Ancestor in Binary Tree in DSA Java - 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 is LCA. Else return the found node.

Execution Sample

DSA Java

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;
}

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	LCA Decision	Visual State
1	Start at root	3	?	?	Recurse left and right	3
2	Recurse left subtree	5	?	?	Recurse left and right	3 -> 5
3	Recurse left subtree	6	null	null	Return 6 (matches p)	3 -> 5 -> 6
4	Recurse right subtree	2	null	null	Return 2 (matches q)	3 -> 5 -> 6, 2
5	At node 5	5	6	2	Both sides non-null, LCA=5	3 -> 5(LCA) -> 6, 2
6	Recurse right subtree	1	null	null	Return null	3 -> 5(LCA) -> 6, 2
7	At root 3	3	5	null	Left non-null, return 5	3(LCA=5)
8	End	3	5	null	LCA found: 5	5 is LCA

💡 Recursion ends when all nodes visited and LCA found at node 5

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 7	Final
root	3	6	2	5	3	3
left	?	6	6	6	5	5
right	?	?	2	2	null	null
LCA	null	null	null	5	5	5

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. See execution_table step 3 and 4 where nodes 6 and 2 match p and q and are returned up.

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 step 5 in execution_table.

What if one side returns null and the other non-null?

We return the non-null side because it means both p and q are in that subtree or one is ancestor of the other. See step 7 where right is null and left is 5.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the LCA decision?

A Both sides null, return null

B Both sides non-null, current node is LCA

C Left side non-null, return left

D Right side non-null, return right

💡 Hint

Check the 'LCA Decision' column at step 5 in execution_table

At which step does the recursion find node matching p?

A Step 3

B Step 2

C Step 4

D Step 5

💡 Hint

Look at 'Node Visited' and 'Operation' columns in execution_table for when p is found

If root was null at start, what would the function return immediately?

A p

B root

C null

D q

💡 Hint

Refer to the base case in code and concept_flow where root == null returns root

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 p or q, return root.
Recurse left and right subtrees.
If both sides return non-null, current node is LCA.
Else return non-null side.
This works for any binary tree, not just BST.

Full Transcript

The Lowest Common Ancestor algorithm starts at the root node and checks if the root is null or matches either of the target nodes p or q. If yes, it returns the root immediately as a candidate ancestor. 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, that side is returned up the recursion. The recursion ends when all nodes are visited and the LCA is found. This approach 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 deepest node that is an ancestor of both nodes

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

D. The root node of the binary tree

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: Clarify the options

   The deepest node that is an ancestor of both nodes correctly describes the LCA. The root node is not always the LCA, and the smallest value or child relationships do not define LCA.

3. Final Answer:

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

4. Quick Check:

   LCA = deepest common ancestor [OK]

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

Common Mistakes:

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

2. Which of the following is the correct Java method signature to find the LCA of two nodes in a binary tree?

easy

A. public void findLCA(TreeNode root, int n1, int n2)

B. public int findLCA(int root, TreeNode n1, TreeNode n2)

C. public TreeNode findLCA(int n1, int n2)

D. public TreeNode findLCA(TreeNode root, int n1, int n2)

Solution

1. Step 1: Analyze method parameters and return type

   The method should take the root node and two node values (or nodes) to find their LCA. It returns the TreeNode representing the LCA.

2. Step 2: Match with options

   public TreeNode findLCA(TreeNode root, int n1, int n2) matches this: it takes root and two integers, returns TreeNode. public int findLCA(int root, TreeNode n1, TreeNode n2) has wrong parameter types, C misses root, D returns void which is incorrect.

3. Final Answer:

   public TreeNode findLCA(TreeNode root, int n1, int n2) -> Option D

4. Quick Check:

   Correct signature includes root and returns TreeNode [OK]

Hint: LCA method needs root and two nodes, returns TreeNode [OK]

Common Mistakes:

• Omitting root parameter
• Wrong return type (void or int)
• Incorrect parameter order or types

3. Given the following binary tree and code snippet, what will be the output?

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

TreeNode lca = findLCA(root, 5, 1);
System.out.println(lca.val);

medium

A. 3

B. 5

C. 1

D. 2

Solution

1. Step 1: Identify 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 their lowest common ancestor

   The lowest common ancestor of 5 and 1 is the root node 3, as it is the deepest node that has both as descendants.

3. Final Answer:

   3 -> Option A

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 child nodes as LCA
• Ignoring tree structure

4. The following Java method is intended to find the LCA of two nodes in a binary tree. What is the bug?

public TreeNode findLCA(TreeNode root, int n1, int n2) {
    if (root == null) return null;
    if (root.val == n1 || root.val == n2) return root;
    TreeNode left = findLCA(root.left, n1, n2);
    TreeNode right = findLCA(root.right, n1, n2);
    if (left != null && right != null) return root;
    if (left != null) return left;
    return right;
}

medium

A. It incorrectly returns root when both left and right are null

B. It returns null when both nodes are the same

C. It does not handle the case when one node is not present in the tree

D. It does not check for null root at the start

Solution

1. Step 1: Understand the method logic

   The method returns root if it matches either node, then recursively searches left and right subtrees. If both sides return non-null, root is LCA.

2. Step 2: Identify missing case

   The method assumes both nodes exist. If one node is missing, it may return the other node incorrectly as LCA without confirming presence of both.

3. Final Answer:

   It does not handle the case when one node is not present in the tree -> Option C

4. Quick Check:

   Missing node presence check causes incorrect LCA [OK]

Hint: Check both nodes exist before returning LCA [OK]

Common Mistakes:

• Ignoring missing node cases
• Assuming both nodes always exist
• Not validating subtree results properly

5. You have a binary tree where nodes can have duplicate values. How would you modify the standard LCA algorithm to correctly find the LCA of two nodes given their references (not values)?

hard

A. Use node references directly instead of comparing values during recursion

B. Use a hash map to store node values and find LCA by values

C. Ignore duplicates and return the first matching value node as LCA

D. Modify the tree to remove duplicates before finding LCA

Solution

1. Step 1: Understand the problem with duplicates

   When values are duplicated, comparing node values is unreliable to identify nodes uniquely.

2. Step 2: Use node references for comparison

   Instead of comparing values, compare the actual node references (memory addresses) to find exact nodes during recursion.

3. Step 3: Adjust algorithm accordingly

   Modify the LCA method to check if current node == target node references, not values.

4. Final Answer:

   Use node references directly instead of comparing values during recursion -> Option A

5. Quick Check:

   Use references, not values, for duplicates [OK]

Hint: Compare node references, not values, when duplicates exist [OK]

Common Mistakes:

• Comparing values instead of references
• Trying to remove duplicates unnecessarily
• Using value-based hash maps causing errors