Lowest Common Ancestor in Binary Tree in DSA Javascript - 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, check if it matches either target node or is null. Recurse left and right. If both sides return nodes, current root is LCA. Otherwise, return the non-null side.

Execution Sample

DSA Javascript

function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return 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 or null	3			No	3
3	Recurse left subtree	5				3 -> 5
4	Check root == p or q or null	5			No	3 -> 5
5	Recurse left subtree	6				3 -> 5 -> 6
6	Check root == p or q or null	6			Yes (node == p)	3 -> 5 -> 6
7	Return node 6	6			6	3 -> 5 -> 6
8	Recurse right subtree	2				3 -> 5 -> 6, 2
9	Check root == p or q or null	2			No	3 -> 5 -> 6, 2
10	Recurse left subtree	7				3 -> 5 -> 6, 2 -> 7
11	Check root == p or q or null	7			Yes (node == q)	3 -> 5 -> 6, 2 -> 7
12	Return node 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 or null	4			No	3 -> 5 -> 6, 2 -> 7, 4
15	Recurse left subtree	null				3 -> 5 -> 6, 2 -> 7, 4
16	Return null	null			null	3 -> 5 -> 6, 2 -> 7, 4
17	Recurse right subtree	null				3 -> 5 -> 6, 2 -> 7, 4
18	Return null	null			null	3 -> 5 -> 6, 2 -> 7, 4
19	Left and right null, return null	4	null	null	null	3 -> 5 -> 6, 2 -> 7, 4
20	Left result 7, right null, return 7	2	7	null	7	3 -> 5 -> 6, 2 -> 7
21	Left result 6, right result 7, both non-null, return root 3	3	6	7	3	3 -> 5 -> 6, 2 -> 7

💡 Returned root 3 as lowest common ancestor because both left and right subtrees contain p and q.

Variable Tracker

Variable	Start	After Step 6	After Step 12	After Step 20	Final
root	3	6	7	2	3
left	undefined	6	6	6	6
right	undefined	undefined	7	7	7
Return Value	undefined	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 and 11 in execution_table where root matches p or q 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 21 where both left (6) and right (7) are non-null, so root 3 is returned.

What happens if one subtree returns null?

We return the non-null subtree result because both nodes are in that subtree or one node is ancestor of the other. See step 20 where left is 7 and right is null, so 7 is returned.

Visual Quiz - 3 Questions

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

A Return null because node 6 is not p or q

B Return node 6 because it matches p

C Return root 3 because it is the ancestor

D Return node 5 because it is the parent

💡 Hint

Check the 'Return Value' column at step 6 and the 'Operation' column for matching p or q.

At which step does the function decide that node 3 is the lowest common ancestor?

A Step 12

B Step 20

C Step 21

D Step 6

💡 Hint

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

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

A Return null because q is missing

B Return node 6 because only p is found

C Return node 7 because q is missing

D Return root 3 anyway

💡 Hint

Refer to the logic in step 20 where one subtree returns a node and the other returns null.

Concept Snapshot

Lowest Common Ancestor (LCA) in Binary Tree:
- If root is null or matches p or q, return root.
- Recursively find LCA in left and right subtrees.
- If both sides return non-null, root is LCA.
- Else return the non-null side.
- Works by bottom-up recursion checking presence of p and q.

Full Transcript

The Lowest Common Ancestor algorithm starts at the root node. If the root is null or matches either target node p or q, it returns root immediately. Otherwise, it recursively searches the left and right subtrees for p and q. If both left and right recursive calls return non-null nodes, it means p and q are found in different subtrees, so the current root is their lowest common ancestor. If only one side returns a non-null node, that node is returned upwards. The process continues until the LCA is found or the search ends. This is shown step-by-step in the execution table where nodes 6 and 7 are found in left and right subtrees of root 3, making 3 the LCA.

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 ancestor concept

   An ancestor of a node is any node on the path from the root to that node.

2. Step 2: Define lowest common ancestor

   The lowest common ancestor is the deepest node that is an ancestor of both given nodes.

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 with smallest value
• Selecting node based on traversal order

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

easy

A. if (root.right == null) return root;

B. if (root.left == null) return root;

C. if (root.value == null) return root;

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

Solution

1. Step 1: Identify base case for recursion

   When the current node is null, it means we've reached the end of a path without finding the target nodes.

2. Step 2: Correct base case condition

   Return null to indicate no ancestor found in this path.

3. Final Answer:

   if (root == null) return null; -> Option D

4. Quick Check:

   Base case returns null on null node [OK]

Hint: Return null when node is null [OK]

Common Mistakes:

• Returning root when left or right child is null
• Checking root.value == null which is invalid
• Missing base case leading to infinite recursion

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

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

function findLCA(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = findLCA(root.left, p, q);
  const right = findLCA(root.right, p, q);
  if (left && right) return root;
  return left ? left : right;
}

const lca = findLCA(root, node5, node1);
console.log(lca.value);

What will be printed?

medium

A. 5

B. 3

C. 1

D. null

Solution

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

   Both nodes 5 and 1 are children of root 3, so recursion finds them in left and right subtrees respectively.

2. Step 2: Determine LCA based on recursion

   Since left and right recursive calls return non-null (nodes 5 and 1), the current root 3 is the LCA.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   LCA of 5 and 1 is 3 [OK]

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

Common Mistakes:

• Returning one of the nodes instead of root
• Confusing node values with LCA
• Ignoring both left and right recursive results

4. The following code attempts to find the LCA but has a bug. What is the error?

function findLCA(root, p, q) {
  if (!root) return null;
  if (root === p || root === q) return root;
  const left = findLCA(root.left, p, q);
  const right = findLCA(root.right, p, q);
  if (left) return left;
  if (right) return right;
  return null;
}

medium

A. It returns left child even if right child is also non-null

B. It does not check if root is null

C. It returns root instead of null when no nodes found

D. It does not handle the case when p or q is missing

Solution

1. Step 1: Analyze return conditions after recursion

   The code returns left if left is non-null without checking right, missing the case when both are non-null.

2. Step 2: Identify missing combined check

   It should return root if both left and right are non-null, indicating LCA found at current root.

3. Final Answer:

   It returns left child even if right child is also non-null -> Option A

4. Quick Check:

   Must check both sides before returning [OK]

Hint: Check both left and right before returning root [OK]

Common Mistakes:

• Returning left without checking right
• Missing combined condition for LCA
• Ignoring null root check

5. Given a binary tree where nodes 2 and 4 are in the left subtree of node 3, and nodes 5 and 6 are in the right subtree of node 3, what is the LCA of nodes 2 and 6?

hard

A. 3

B. 2

C. 4

D. 5

Solution

1. Step 1: Understand tree structure

   Nodes 2 and 4 are in left subtree of 3; nodes 5 and 6 are in right subtree of 3.

2. Step 2: Find common ancestor of nodes 2 and 6

   Since 2 is in left subtree and 6 is in right subtree, their lowest common ancestor is the root node 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   LCA of nodes in opposite subtrees is root [OK]

Hint: LCA of nodes in different subtrees is their root [OK]

Common Mistakes:

• Choosing one of the nodes instead of ancestor
• Confusing sibling nodes as LCA
• Ignoring tree structure