Lowest Common Ancestor in Binary Tree in DSA C

Mental Model

Find the closest shared parent node of two given nodes in a tree by exploring paths from the root.

Analogy: Imagine a family tree where you want to find the nearest common grandparent of two cousins by tracing their parents upwards until they meet.

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

Here, 5 and 1's lowest common ancestor is 3.

Dry Run Walkthrough

Input: Binary tree with nodes 3,5,1,6,2,0,8,7,4; find LCA of nodes 5 and 1

Goal: Find the lowest common ancestor node of 5 and 1 in the tree

Step 1: Start at root node 3, check if it matches 5 or 1

3 ↑
/ \
5  1
...

Why: We begin from the root to explore both subtrees for the target nodes

Step 2: Recurse left subtree from node 5, check if it matches 5 or 1

3
/ ↑ \
5  1
...

Why: Check left subtree for presence of nodes 5 or 1

Step 3: Node 5 matches one target node, return node 5 up the call stack

3
/ [5] \
5  1
...

Why: Found one target node, so return it to parent

Step 4: Recurse right subtree from node 1, check if it matches 5 or 1

3
/ 5 \ ↑
5  1
...

Why: Check right subtree for presence of nodes 5 or 1

Step 5: Node 1 matches the other target node, return node 1 up the call stack

3
/ 5 \ [1]
5  1
...

Why: Found second target node, return it to parent

Step 6: At node 3, both left and right returned non-null nodes (5 and 1), so node 3 is LCA

[3]
/ 5 \ 1
5  1
...

Why: Both targets found in different subtrees, so current node is their lowest common ancestor

Result:

3 [LCA]
/ 5 \ 1
5  1
...

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Define binary tree node
typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
} Node;

// Create new node
Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Find Lowest Common Ancestor
Node* lowestCommonAncestor(Node* root, Node* p, Node* q) {
    if (root == NULL) return NULL; // base case: empty subtree
    if (root == p || root == q) return root; // found one target node

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

    if (left != NULL && right != NULL) return root; // targets found in different subtrees
    if (left != NULL) return left; // targets found only in left subtree
    return right; // targets found only in right subtree or none
}

// Print node value
void printNode(Node* node) {
    if (node != NULL) printf("%d\n", node->val);
    else printf("NULL\n");
}

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

    Node* p = root->left; // node 5
    Node* q = root->right; // node 1

    Node* lca = lowestCommonAncestor(root, p, q);
    printf("Lowest Common Ancestor: ");
    printNode(lca);

    return 0;
}

if (root == NULL) return NULL;

stop recursion if subtree is empty

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

return current node if it matches one target

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

search left subtree for targets

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

search right subtree for targets

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

if targets found in both subtrees, current node is LCA

if (left != NULL) return left;

if targets found only in left subtree, propagate left result

return right;

otherwise propagate right result or NULL

Output

Lowest Common Ancestor: 3

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 paths for both nodes and then comparing, this approach uses less space and is simpler

Edge Cases

One or both nodes not present in tree

Function returns NULL or the node found; no false LCA

DSA C

if (root == NULL) return NULL;

Both nodes are the same

Function returns that node as LCA immediately

DSA C

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

Tree with only root node

If targets are root, returns root; else NULL

DSA C

if (root == NULL) return NULL;

When to Use This Pattern

When asked to find the nearest shared ancestor of two nodes in a tree, use the Lowest Common Ancestor pattern by recursively searching subtrees and combining results.

Common Mistakes

Mistake: Returning the first found node without checking both subtrees
Fix: Check both left and right subtrees and return current node if both sides contain targets

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 closest shared parent node of two given nodes in a binary tree.

Use when you need to find the lowest common ancestor of two nodes in a tree structure.

The key insight is that if both targets 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 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