Lowest Common Ancestor in Binary Tree in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Lowest Common Ancestor (LCA) in a binary tree?

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

beginner

In the context of LCA, what does it mean if a node is 'ancestor' of itself?

It means that when searching for LCA, a node can be considered as its own ancestor, so if one node is the ancestor of the other, the LCA is the ancestor node itself.

intermediate

What is the base case in the recursive approach to find LCA in a binary tree?

If the current node is null or matches one of the target nodes, return the current node as a potential ancestor.

intermediate

How does the recursive LCA algorithm decide the LCA when both left and right recursive calls return non-null nodes?

If both left and right recursive calls return non-null nodes, it means the current node is the lowest node where the two target nodes split, so the current node is the LCA.

intermediate

Why is the LCA algorithm for a binary tree different from that for a binary search tree?

Because a binary tree has no ordering property, the algorithm must search both left and right subtrees, while a binary search tree uses node values to decide which subtree to search, making it more efficient.

What is the first step in the recursive LCA algorithm for a binary tree?

A Return the root node immediately

B Check if the current node is null or matches one of the target nodes

C Search only the left subtree

D Search only the right subtree

The algorithm first checks if the current node is null or matches one of the target nodes to handle base cases.

If the left recursive call returns a node and the right recursive call returns null, what does the LCA algorithm return?

A The current node

B The node returned by the right recursive call

C The node returned by the left recursive call

D Null

If only one side returns a non-null node, that node is returned upward as a potential ancestor.

When both left and right recursive calls return non-null nodes, what does the algorithm conclude?

A Continue searching deeper

B No common ancestor found

C Return null

D Current node is the Lowest Common Ancestor

Both sides returning non-null means the current node is where the two nodes split, so it is the LCA.

Can a node be the Lowest Common Ancestor of itself and another node?

A Yes

B No

C Only if it is the root

D Only if it has two children

A node can be an ancestor of itself, so it can be the LCA if the other node is in its subtree.

Why does the LCA algorithm for a binary tree need to search both left and right subtrees?

A Because there is no ordering property in a binary tree

B Because the tree is always balanced

C Because nodes are sorted

D Because it only has one child

Binary trees do not have ordering, so both subtrees must be searched to find the nodes.

Explain the recursive approach to find the Lowest Common Ancestor in a binary tree.

Think about how recursion explores the tree and combines results.

Describe why the Lowest Common Ancestor algorithm differs between a binary tree and a binary search tree.

Consider the properties of each tree type.

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