Lowest Common Ancestor in Binary Tree in DSA C++

Mental Model

Find the shared parent node where two nodes meet first when moving up the tree.

Analogy: Like finding the closest common boss for two employees in a company hierarchy tree.

       1
      / \
     2   3
    / \   \
   4   5   6

Dry Run Walkthrough

Input: Binary tree: 1->2,3; 2->4,5; 3->null,6; Find LCA of nodes 4 and 5

Goal: Find the lowest node that is an ancestor of both 4 and 5

Step 1: Start at root node 1, check left and right subtrees for nodes 4 and 5

At node 1: searching left subtree -> 2, right subtree -> 3

Why: We begin from the top to find where both nodes appear in subtrees

Step 2: Move to left child 2, check left subtree for node 4

At node 2: left child -> 4, right child -> 5

Why: Node 2 is parent of 4 and 5, so check its children

Step 3: Find node 4 at left child of 2, return node 4 up

Found node 4 at left child of 2

Why: One target node found, return it to parent call

Step 4: Find node 5 at right child of 2, return node 5 up

Found node 5 at right child of 2

Why: Second target node found, return it to parent call

Step 5: At node 2, both left and right returned non-null (4 and 5), so node 2 is LCA

LCA found at node 2

Why: Both nodes found in different subtrees of 2, so 2 is their lowest common ancestor

Result:

2 is the lowest common ancestor of nodes 4 and 5

Annotated Code

DSA C++

#include <iostream>
using namespace std;

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

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr) return nullptr; // base case: empty subtree
    if (root == p || root == q) return root; // found one target node

    TreeNode* left = lowestCommonAncestor(root->left, p, q); // search left subtree
    TreeNode* right = lowestCommonAncestor(root->right, p, q); // search right subtree

    if (left != nullptr && right != nullptr) return root; // both nodes found in different subtrees
    if (left != nullptr) return left; // both nodes in left subtree
    return right; // both nodes in right subtree or none found
}

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

    TreeNode* p = root->left->left; // node 4
    TreeNode* q = root->left->right; // node 5

    TreeNode* lca = lowestCommonAncestor(root, p, q);
    if (lca != nullptr) {
        cout << lca->val << "\n";
    } else {
        cout << "No common ancestor found\n";
    }
    return 0;
}

if (root == nullptr) return nullptr;

stop if subtree is empty

if (root == p || root == q) return root;

return node if it matches one target

TreeNode* left = lowestCommonAncestor(root->left, p, q);

search left subtree for targets

TreeNode* right = lowestCommonAncestor(root->right, p, q);

search right subtree for targets

if (left != nullptr && right != nullptr) return root;

if targets found in both subtrees, current node is LCA

if (left != nullptr) return left;

if both targets in left subtree, return left result

return right;

otherwise return right subtree result

Output

2

Complexity Analysis

Time: O(n) because we visit each node once in the worst case

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to storing parent pointers and paths, this method uses no extra memory for parent maps and is simpler

Edge Cases

Empty tree (root == nullptr)

Function returns nullptr indicating no common ancestor found

DSA C++

if (root == nullptr) return nullptr;

One node is ancestor of the other

Ancestor node is returned as LCA

DSA C++

if (root == p || root == q) return root;

Tree with only one node which is both p and q

That node is returned as LCA

DSA C++

if (root == p || root == q) return root;

When to Use This Pattern

When asked to find the shared ancestor of two nodes in a tree without parent pointers, use the recursive LCA pattern to find the lowest common ancestor efficiently.

Common Mistakes

Mistake: Returning the first found node without checking both subtrees
Fix: Check both left and right subtree results to confirm both nodes are found before returning current node as LCA

Mistake: Not handling the case when one node is ancestor of the other
Fix: Return current node immediately if it matches either target node

Summary

Finds the lowest node in a binary tree that is ancestor to two given nodes.

Use when you need to find the closest shared parent of two nodes in a tree without parent links.

The key insight is that if both nodes are found in different subtrees of a node, that node is their lowest common ancestor.

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