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.