Why Lowest Common Ancestor in Binary Tree in DSA C?

The Big Idea

What if you could instantly find the closest shared boss of two employees without tracing every step?

The Scenario

Imagine you have a family tree drawn on paper, and you want to find the closest common grandparent of two cousins. You try to trace their paths manually, going up the tree, but it quickly becomes confusing and slow as the tree grows.

The Problem

Manually tracing paths for each node to find their common ancestor is slow and error-prone. You might lose track of nodes or repeat work, especially if the tree is large or unbalanced. It's like searching for a needle in a haystack without a map.

The Solution

The Lowest Common Ancestor (LCA) algorithm helps find the closest shared ancestor of two nodes in a binary tree efficiently. It uses a smart recursive approach to explore the tree just once, returning the answer without extra searching or storing paths.

Before vs After

✗ Before

Node* findAncestor(Node* root, Node* node1, Node* node2) {
  // Manually find paths for node1 and node2
  // Compare paths to find common ancestor
  // Complex and slow
}

✓ After

Node* findLCA(Node* root, Node* node1, Node* node2) {
  if (!root) return NULL;
  if (root == node1 || root == node2) return root;
  Node* left = findLCA(root->left, node1, node2);
  Node* right = findLCA(root->right, node1, node2);
  if (left && right) return root;
  return left ? left : right;
}

What It Enables

This concept enables quick and reliable discovery of relationships in hierarchical data, making complex tree queries simple and fast.

Real Life Example

In a company's organizational chart, finding the lowest common manager of two employees helps decide who should approve joint projects or resolve conflicts.

Key Takeaways

Manual search for common ancestors is slow and confusing.

LCA uses recursion to find the closest shared ancestor efficiently.

It simplifies complex tree queries in many real-world hierarchies.

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