Lowest Common Ancestor in Binary Tree in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find the Lowest Common Ancestor (LCA) output

What is the output of the following code that finds the LCA of nodes 5 and 1 in the given binary tree?

DSA C

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

struct Node* lca(struct Node* root, int p, int q) {
    if (!root) return NULL;
    if (root->val == p || root->val == q) return root;
    struct Node* left = lca(root->left, p, q);
    struct Node* right = lca(root->right, p, q);
    if (left && right) return root;
    return left ? left : right;
}

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

// Call: lca(root, 5, 1)

// Output the value of the LCA node found.

A 2

B 5

C 1

D 3

💡 Hint

The LCA is the lowest node that has both nodes as descendants.

Nodes 5 and 1 are children of 3, so 3 is their lowest common ancestor.

❓ Predict Output

intermediate

LCA output when one node is ancestor of the other

What is the output of the code when finding the LCA of nodes 5 and 4 in the same binary tree?

DSA C

/* Same Node struct and lca function as before */

// Call: lca(root, 5, 4)

// Output the value of the LCA node found.

A 3

B 5

C 2

D 4

💡 Hint

If one node is ancestor of the other, the ancestor is the LCA.

Node 5 is an ancestor of node 4, so the LCA is node 5 itself.

🔧 Debug

advanced

Identify the error in LCA function

What error will the following LCA function cause when called with nodes not present in the tree?

DSA C

struct Node* lca(struct Node* root, int p, int q) {
    if (!root) return NULL;
    if (root->val == p || root->val == q) return root;
    struct Node* left = lca(root->left, p, q);
    struct Node* right = lca(root->right, p, q);
    if (left && right) return root;
    return left ? left : right;
}

// Call: lca(root, 10, 11) where 10 and 11 are not in tree

A Returns NULL without error

B Segmentation fault due to null pointer dereference

C Returns root node incorrectly

D Infinite recursion causing stack overflow

💡 Hint

Check what happens when nodes are not found in either subtree.

The function returns NULL safely if neither node is found; no error occurs.

🧠 Conceptual

advanced

Understanding LCA in Binary Tree vs Binary Search Tree

Which statement correctly distinguishes the LCA approach in a Binary Tree vs a Binary Search Tree (BST)?

A In BST, LCA requires checking both subtrees; in Binary Tree, node values guide the search.

B In Binary Tree, LCA is always the root; in BST, LCA is always a leaf node.

C In BST, LCA can be found using node values comparison; in Binary Tree, recursion is needed to search both subtrees.

D Both Binary Tree and BST use the same approach by comparing node values only.

💡 Hint

BST has ordered values, Binary Tree does not.

BST property allows LCA search by comparing values; Binary Tree requires full subtree search.

🚀 Application

expert

LCA in a Binary Tree with Parent Pointers

Given a binary tree where each node has a pointer to its parent, which approach is the most efficient to find the LCA of two nodes p and q?

A Traverse from p and q upwards, storing ancestors of p in a set, then find first ancestor of q in that set.

B Perform BFS from root to find paths to p and q, then compare paths to find LCA.

C Use recursion from root to find LCA by searching both subtrees for p and q.

D Convert tree to BST and then use BST LCA method.

💡 Hint

Parent pointers allow upward traversal without root access.

Storing ancestors of one node and checking the other node's ancestors is efficient and uses O(h) time and space, where h is tree height.

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