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

Practice - 5 Tasks

1fill in blank

easy

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

DSA C

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 wrong base case.

Using comparison operators like '<=' or '>' is incorrect for pointers.

The base case checks if the current node is NULL using '=='.

2fill in blank

medium

Complete the code to check if the current node matches either target node p or q.

DSA C

if (root == [1] || root == [2]) return root;

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

Aq

Bp

CNULL

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Using NULL instead of p or q.

Using root instead of target nodes.

We check if the current node is equal to p or q to return it immediately.

3fill in blank

hard

Fix the error in the recursive call to search the left subtree.

DSA C

struct TreeNode* left = [1](root->left, p, q);

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

AlowestCommonAncestor

BgetAncestor

CfindLCA

Dsearch

Attempts:

3 left

💡 Hint

Common Mistakes

Using undefined function names causes compilation errors.

Using different function names breaks recursion.

The function calls itself recursively using its own name 'lowestCommonAncestor'.

4fill in blank

hard

Fill both blanks to return the correct ancestor based on left and right subtree results.

DSA C

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

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

Aroot

Bleft

Cright

DNULL

Attempts:

3 left

💡 Hint

Common Mistakes

Returning NULL when both sides are valid.

Returning the wrong subtree pointer.

If both left and right are not NULL, root is the ancestor. Otherwise, return the non-NULL child.

5fill in blank

hard

Fill all three blanks to complete the function signature and return type.

DSA C

[1] [2] [3](struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (root == NULL) return NULL;
    if (root == p || root == q) return root;
    struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
    struct 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'

Astruct

BTreeNode*

ClowestCommonAncestor

Dvoid

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'void' as return type causes errors.

Omitting 'struct' keyword in C causes compilation errors.

The function returns a pointer to a TreeNode, so the signature is 'struct TreeNode* lowestCommonAncestor(...)'.

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 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: Differentiate from other nodes

   The root node is not always the LCA unless both nodes are in different subtrees of the root. The smallest value or traversal order does not define LCA.

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 based on value instead of position
• Using traversal order to find LCA

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

easy

A. if (root->left == NULL) return root;

B. if (root == NULL) return NULL;

C. if (root->right == NULL) return root;

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

Solution

1. Step 1: Identify the base case for recursion

   When the current node is NULL, it means we reached the end of a path without finding the target nodes, so return NULL.

2. Step 2: Check other options

   Returning root when left or right child is NULL is incorrect because the node itself may not be the LCA. Returning root when root is NULL is invalid.

3. Final Answer:

   if (root == NULL) return NULL; -> Option B

4. Quick Check:

   Base case: root NULL returns NULL [OK]

Hint: Return NULL when node is NULL in recursion [OK]

Common Mistakes:

• Returning root instead of NULL when node is NULL
• Checking only left or right child for base case
• Returning root when root is NULL

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

struct Node {
  int val;
  struct Node *left, *right;
};

struct Node* findLCA(struct Node* root, int n1, int n2) {
  if (root == NULL) return NULL;
  if (root->val == n1 || root->val == n2) return root;
  struct Node* left_lca = findLCA(root->left, n1, n2);
  struct Node* right_lca = findLCA(root->right, n1, n2);
  if (left_lca && right_lca) return root;
  return (left_lca != NULL) ? left_lca : right_lca;
}

// Tree structure:
//       3
//      / \
//     5   1
//    / \ / \
//   6  2 0  8
//     / \
//    7   4

// Call: findLCA(root, 5, 1);

What node value will the function return?

medium

A. 3

B. 5

C. 1

D. 2

Solution

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

   Starting at root (3), neither 5 nor 1 matches root. Recursively check left subtree (root 5) and right subtree (root 1). Left subtree returns node 5, right subtree returns node 1.

2. Step 2: Determine LCA based on returned nodes

   Since both left_lca and right_lca are non-NULL, the current root (3) is the LCA.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   LCA(5,1) = 3 [OK]

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

Common Mistakes:

• Returning one of the nodes instead of their ancestor
• Confusing node values with LCA
• Not checking both left and right subtree results

4. The following code attempts to find the LCA of two nodes in a binary tree but has a bug: <pre>struct Node* findLCA(struct Node* root, int n1, int n2) { if (root == NULL) return NULL; if (root->val == n1 || root->val == n2) return root; struct Node* left_lca = findLCA(root->left, n1, n2); struct Node* right_lca = findLCA(root->right, n1, n2); if (left_lca != NULL && right_lca != NULL) return root; else if (left_lca != NULL) return left_lca; else if (right_lca != NULL) return right_lca; return NULL; } // Bug: The function sometimes returns NULL if one of the nodes does not exist in the tree. What is the likely cause of this bug?

medium

A. The function incorrectly returns root when both children are NULL

B. The base case returns NULL instead of root

C. The function does not handle the case when n1 equals n2

D. The function does not check if both nodes exist in the tree before finding LCA

Solution

1. Step 1: Analyze the function's behavior

   The function returns NULL if it does not find either node in a subtree. If one node is missing in the tree, the function may return NULL even if the other node exists.

2. Step 2: Identify missing existence check

   The function assumes both nodes exist. Without verifying both nodes are present, it can return NULL incorrectly.

3. Final Answer:

   The function does not check if both nodes exist in the tree before finding LCA -> Option D

4. Quick Check:

   Check node existence before LCA [OK]

Hint: Verify both nodes exist before LCA search [OK]

Common Mistakes:

• Ignoring node existence check
• Assuming base case handles all scenarios
• Not handling identical nodes input

5. Given a binary tree where nodes can have duplicate values, which modification is necessary to correctly find the Lowest Common Ancestor of two nodes identified by their values?

hard

A. Modify the function to find nodes by their unique memory addresses or pointers instead of values

B. Use inorder traversal to find the first occurrence of each value

C. Return the node with the smaller value as LCA

D. Ignore duplicates and return the first matching node found

Solution

1. Step 1: Understand the problem with duplicates

   When values are not unique, identifying nodes by value alone can lead to incorrect LCA because multiple nodes share the same value.

2. Step 2: Use unique identifiers for nodes

   Using unique memory addresses or pointers ensures the function finds the exact nodes intended, avoiding confusion from duplicates.

3. Final Answer:

   Modify the function to find nodes by their unique memory addresses or pointers instead of values -> Option A

4. Quick Check:

   Use unique node references for duplicates [OK]

Hint: Use node pointers, not values, when duplicates exist [OK]

Common Mistakes:

• Assuming values are unique identifiers
• Using traversal order to pick nodes
• Ignoring duplicates causing wrong LCA