Lowest Common Ancestor in Binary Tree in DSA C - Build from Scratch

Lowest Common Ancestor in Binary Tree

📖 Scenario: You are working with a family tree represented as a binary tree. Each node represents a family member. You want to find the closest common ancestor of two given family members.

🎯 Goal: Build a program in C that creates a binary tree, sets two target nodes, finds their lowest common ancestor (LCA), and prints the LCA's value.

📋 What You'll Learn

Create a binary tree with exactly 7 nodes with values 1 to 7 arranged as a perfect binary tree

Create two pointers to nodes with values 4 and 5

Implement a function lowestCommonAncestor that finds the LCA of two given nodes

Print the value of the LCA node

💡 Why This Matters

🌍 Real World

Finding the lowest common ancestor is useful in family trees, organizational charts, and file directory structures to find shared ancestors or common points.

💼 Career

Understanding tree traversal and recursive algorithms is important for software engineering roles involving data structures, databases, and system design.

1

Create the binary tree nodes and link them

Create a struct TreeNode with an int val and two pointers left and right. Then create 7 nodes named node1 to node7 with values 1 to 7. Link them to form a perfect binary tree with node1 as root, node2 and node3 as children of node1, and so on.

DSA C

# Define struct TreeNode
// Create nodes node1 to node7 with values 1 to 7
// Link nodes to form the tree
// Your code here

Hint

Define the struct first. Then create each node with its value and NULL children. Finally, link the nodes to form the tree.

2

Create pointers to the two target nodes

Create two pointers named p and q that point to node4 and node5 respectively.

DSA C

#include 
#include 

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

int main() {
    TreeNode node1 = {1, NULL, NULL};
    TreeNode node2 = {2, NULL, NULL};
    TreeNode node3 = {3, NULL, NULL};
    TreeNode node4 = {4, NULL, NULL};
    TreeNode node5 = {5, NULL, NULL};
    TreeNode node6 = {6, NULL, NULL};
    TreeNode node7 = {7, NULL, NULL};

    node1.left = &node2;
    node1.right = &node3;
    node2.left = &node4;
    node2.right = &node5;
    node3.left = &node6;
    node3.right = &node7;

    // Create pointers p and q to node4 and node5
    // Your code here

    return 0;
}

Hint

Use pointers to point to the existing nodes node4 and node5.

3

Implement the lowestCommonAncestor function

Write a function TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) that returns the lowest common ancestor of nodes p and q in the binary tree rooted at root. Use recursion and return root if it matches p or q. Otherwise, search left and right subtrees and return the node where both sides are found.

DSA C

#include 
#include 

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q);

int main() {
    TreeNode node1 = {1, NULL, NULL};
    TreeNode node2 = {2, NULL, NULL};
    TreeNode node3 = {3, NULL, NULL};
    TreeNode node4 = {4, NULL, NULL};
    TreeNode node5 = {5, NULL, NULL};
    TreeNode node6 = {6, NULL, NULL};
    TreeNode node7 = {7, NULL, NULL};

    node1.left = &node2;
    node1.right = &node3;
    node2.left = &node4;
    node2.right = &node5;
    node3.left = &node6;
    node3.right = &node7;

    TreeNode *p = &node4;
    TreeNode *q = &node5;

    // Your code here

    return 0;
}

// Implement lowestCommonAncestor function below
// Your code here

Hint

Check if root is NULL or matches p or q. Recursively search left and right. If both sides return non-NULL, root is LCA. Otherwise return the non-NULL side.

4

Call the function and print the LCA value

Call lowestCommonAncestor with node1 as root and pointers p and q. Store the result in TreeNode* lca. Then print the value of lca->val using printf.

DSA C

#include 
#include 

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == NULL || root == p || root == q) {
        return root;
    }
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left != NULL && right != NULL) {
        return root;
    }
    return left != NULL ? left : right;
}

int main() {
    TreeNode node1 = {1, NULL, NULL};
    TreeNode node2 = {2, NULL, NULL};
    TreeNode node3 = {3, NULL, NULL};
    TreeNode node4 = {4, NULL, NULL};
    TreeNode node5 = {5, NULL, NULL};
    TreeNode node6 = {6, NULL, NULL};
    TreeNode node7 = {7, NULL, NULL};

    node1.left = &node2;
    node1.right = &node3;
    node2.left = &node4;
    node2.right = &node5;
    node3.left = &node6;
    node3.right = &node7;

    TreeNode *p = &node4;
    TreeNode *q = &node5;

    // Call lowestCommonAncestor and print the result
    // Your code here

    return 0;
}

Hint

Call the function with root as &node1 and print the value of the returned node.

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