Lowest Common Ancestor in Binary Tree in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the current node is null.

DSA Java

if (root [1] null) return null;

Drag options to blanks, or click blank then click option'

A=>

B=

C!=

D==

Attempts:

3 left

💡 Hint

Common Mistakes

Using '=' instead of '==' causes assignment, not comparison.

Using '!=' would check for not null, which is opposite.

We use '==' to compare if root is null in Java.

2fill in blank

medium

Complete the code to check if the current node matches either of the target nodes.

DSA Java

if (root [1] p || root [1] q) return root;

Drag options to blanks, or click blank then click option'

A==

B=

C!=

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '=' instead of '==' causes assignment, not comparison.

Using '!=' or '>' will not correctly check equality.

We use '==' to check if root equals p or q.

3fill in blank

hard

Fix the error in the recursive calls to search left and right subtrees.

DSA Java

TreeNode left = lowestCommonAncestor(root.[1], p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);

Drag options to blanks, or click blank then click option'

Aleft

Bright

CleftChild

Dleft.left

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'right' instead of 'left' accesses the wrong subtree.

Using 'leftChild' or 'left.left' may not match the node definition.

The left child of root is accessed by 'left' in this code context.

4fill in blank

hard

Fill both blanks to return the correct ancestor based on recursive results.

DSA Java

if (left != null && right != null) return [1];
return left != null ? [2] : right;

Drag options to blanks, or click blank then click option'

Aroot

Bleft

Cright

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 'left' when both sides are non-null instead of root.

Returning 'right' instead of 'left' in the ternary operator.

If both left and right are non-null, root is the ancestor; otherwise return the non-null child.

5fill in blank

hard

Fill all three blanks to complete the full method for Lowest Common Ancestor.

DSA Java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root [1] null) return null;
    if (root [2] p || root [2] q) return root;
    TreeNode left = lowestCommonAncestor(root.[3], p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

Drag options to blanks, or click blank then click option'

A==

Bleft

C!=

D=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '=' instead of '==' for comparisons.

Using '!=' instead of '==' for equality checks.

Using wrong field name for left child.

Use '==' for comparisons and 'left' to access the left child node.

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