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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of LCA function for given binary tree and nodes

What is the output of the following C++ code that finds the Lowest Common Ancestor (LCA) of two nodes in a binary tree?

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

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

int main() {
    Node* root = new Node(3);
    root->left = new Node(5);
    root->right = new Node(1);
    root->left->left = new Node(6);
    root->left->right = new Node(2);
    root->right->left = new Node(0);
    root->right->right = new Node(8);
    root->left->right->left = new Node(7);
    root->left->right->right = new Node(4);

    Node* lca = findLCA(root, 7, 4);
    if (lca) std::cout << lca->val << std::endl;
    else std::cout << "No LCA found" << std::endl;
    return 0;
}

A 3

B 5

C 7

D 2

💡 Hint

Think about where nodes 7 and 4 are located in the tree and which node is their closest shared ancestor.

The nodes 7 and 4 are both children of node 2. The function finds that node 2 is the lowest node in the tree that has both 7 and 4 as descendants. Hence, the output is 2.

🧠 Conceptual

intermediate

Understanding the base case in LCA recursive function

In the recursive function to find the Lowest Common Ancestor (LCA) in a binary tree, what is the purpose of the base case that returns the root if root's value matches either of the target nodes?

A It stops recursion when one of the target nodes is found, marking a potential ancestor.

B It skips the current node and continues searching in children.

C It immediately returns the root's parent node.

D It returns null to indicate the node is not found here.

💡 Hint

Think about why the function needs to know when it has found one of the nodes.

The base case returns the current node when it matches one of the target nodes. This signals that one target node has been found, which helps the recursion identify the ancestor nodes.

🔧 Debug

advanced

Identify the error in this LCA function variant

What error will the following C++ code produce when trying to find the LCA of nodes 5 and 1?

DSA C++

Node* findLCA(Node* root, int n1, int n2) {
    if (!root) return nullptr;
    if (root->val == n1 || root->val == n2) return root;
    Node* left_lca = findLCA(root->left, n1, n2);
    Node* right_lca = findLCA(root->right, n1, n2);
    if (left_lca && right_lca) return root;
    if (left_lca) return left_lca;
    if (right_lca) return right_lca;
    // Missing return statement here
    return nullptr;
}

A Compilation error due to missing return statement

B Runtime error: segmentation fault

C Returns nullptr without error

D Returns wrong node value

💡 Hint

Check if all code paths return a value.

The function lacks a return statement if both left_lca and right_lca are nullptr. This causes a compilation error because the function expects a return value on all paths.

❓ Predict Output

advanced

Output of LCA function when one node is not present

What is the output of the following code when searching for the LCA of nodes 5 and 10, where 10 does not exist in the tree?

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

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

int main() {
    Node* root = new Node(3);
    root->left = new Node(5);
    root->right = new Node(1);
    root->left->left = new Node(6);
    root->left->right = new Node(2);
    root->right->left = new Node(0);
    root->right->right = new Node(8);
    root->left->right->left = new Node(7);
    root->left->right->right = new Node(4);

    Node* lca = findLCA(root, 5, 10);
    if (lca) std::cout << lca->val << std::endl;
    else std::cout << "No LCA found" << std::endl;
    return 0;
}

A 3

B No LCA found

C 5

D 10

💡 Hint

Consider what happens when one node is found but the other is missing.

The function returns the node that it finds first (5). Since 10 is not in the tree, the function returns 5 as the LCA, which is the node found.

🧠 Conceptual

expert

Why does the LCA algorithm work without parent pointers?

Why can the Lowest Common Ancestor (LCA) be found in a binary tree using only recursive calls without storing parent pointers?

A Because the tree nodes store references to their ancestors internally.

B Because recursion explores all paths and returns nodes upward, allowing the function to detect where paths to both nodes diverge.

C Because the algorithm uses a global variable to track parents during traversal.

D Because the tree is always a binary search tree, so parent pointers are unnecessary.

💡 Hint

Think about how recursion returns information from child nodes to parent nodes.

The recursive calls return nodes upward when they find one of the target nodes. When both left and right recursive calls return non-null, it means the current node is the lowest node where paths to both targets split, identifying the LCA without needing parent pointers.

Practice

1. What is the Lowest Common Ancestor (LCA) of two nodes in a binary tree?

easy

A. The deepest node that is an ancestor of both nodes

B. The root node of the binary tree

C. The node with the smallest value between the two nodes

D. The node that appears first in an inorder traversal

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

   It is not necessarily the root or the node with smallest value, but the common ancestor closest to the two nodes.

3. Final Answer:

   The deepest node that is an ancestor of both nodes -> Option A

4. Quick Check:

   LCA = deepest common ancestor [OK]

Hint: LCA is the lowest node common to both paths [OK]

Common Mistakes:

• Confusing LCA with root node
• Choosing node by value instead of position
• Thinking LCA is the first visited node in traversal

2. Which of the following is the correct C++ function signature to find LCA in a binary tree node structure?

easy

A. int findLCA(int root, int n1, int n2);

B. TreeNode* findLCA(TreeNode* root, int n1, int n2);

C. void findLCA(TreeNode root, int n1, int n2);

D. TreeNode findLCA(TreeNode root, int n1, int n2);

Solution

1. Step 1: Analyze parameter types

   The function should accept a pointer to the root node and two integer values representing node keys.

2. Step 2: Analyze return type

   The function returns a pointer to the TreeNode representing the LCA, so return type must be TreeNode*.

3. Final Answer:

   TreeNode* findLCA(TreeNode* root, int n1, int n2); -> Option B

4. Quick Check:

   Function signature with pointers and correct return type [OK]

Hint: LCA function returns pointer to TreeNode [OK]

Common Mistakes:

• Using value instead of pointer for root
• Returning int instead of TreeNode*
• Passing root by value causing copy

3. Given the following binary tree and code snippet, what will be the output?

#include <iostream>
struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* findLCA(TreeNode* root, int n1, int n2) {
  if (!root) return nullptr;
  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 && right) return root;
  return left ? left : right;
}

int main() {
  TreeNode* root = new TreeNode(3);
  root->left = new TreeNode(5);
  root->right = new TreeNode(1);
  root->left->left = new TreeNode(6);
  root->left->right = new TreeNode(2);
  root->right->left = new TreeNode(0);
  root->right->right = new TreeNode(8);
  TreeNode* lca = findLCA(root, 6, 2);
  std::cout << lca->val << std::endl;
  return 0;
}

medium

A. 6

B. 3

C. 2

D. 5

Solution

1. Step 1: Trace the tree structure and nodes

   Nodes 6 and 2 are both children of node 5 in the tree.

2. Step 2: Apply LCA logic

   Since 5 is the lowest node that has both 6 and 2 as descendants, the function returns node 5.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   LCA(6,2) = 5 [OK]

Hint: LCA is ancestor closest to both nodes [OK]

Common Mistakes:

• Choosing root 3 instead of node 5
• Confusing child nodes as LCA
• Returning one of the input nodes incorrectly

4. Identify the bug in the following LCA function and select the correct fix:

TreeNode* findLCA(TreeNode* root, int n1, int n2) {
  if (!root) return nullptr;
  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 && right) return root;
  if (left) return right;
  return right;
}

medium

A. Add a check for root being nullptr after recursive calls

B. Change 'if (left && right) return root;' to 'return nullptr;'

C. Change 'if (left) return right;' to 'if (left) return left;'

D. Change return type to int instead of TreeNode*

Solution

1. Step 1: Analyze the return statements

   The code incorrectly returns 'right' when 'left' is true, which is wrong logic.

2. Step 2: Correct the return for left subtree

   It should return 'left' when 'left' is true and 'right' is false to propagate the found node correctly.

3. Final Answer:

   Change 'if (left) return right;' to 'if (left) return left;' -> Option C

4. Quick Check:

   Return correct subtree pointer [OK]

Hint: Return the non-null subtree pointer correctly [OK]

Common Mistakes:

• Returning wrong subtree pointer
• Ignoring nullptr checks
• Changing return type unnecessarily

5. Given a binary tree where nodes may not contain unique values, which modification is necessary to correctly find the LCA of two nodes identified by their pointers (not values)?

hard

A. Modify the LCA function to compare node pointers directly instead of values

B. Use node values for comparison as usual, ignoring pointer identity

C. Sort the tree nodes before finding LCA to ensure uniqueness

D. Replace the binary tree with a binary search tree for unique values

Solution

1. Step 1: Understand the problem with duplicate values

   If nodes have duplicate values, comparing values is ambiguous and can lead to wrong LCA.

2. Step 2: Use pointer comparison

   Comparing node pointers directly ensures the exact nodes are identified regardless of value duplicates.

3. Step 3: Modify function accordingly

   The LCA function should check if the current node pointer equals either of the target node pointers.

4. Final Answer:

   Modify the LCA function to compare node pointers directly instead of values -> Option A

5. Quick Check:

   Compare pointers, not values, for duplicates [OK]

Hint: Compare node addresses, not values, for duplicates [OK]

Common Mistakes:

• Using values for comparison with duplicates
• Assuming tree is BST to fix duplicates
• Sorting nodes which is unnecessary