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

Lowest Common Ancestor in Binary Tree

📖 Scenario: You are working on a family tree application. You want to find the closest common ancestor of two family members in the tree.

🎯 Goal: Build a program to find the Lowest Common Ancestor (LCA) of two nodes in a binary tree.

📋 What You'll Learn

Create a binary tree with specific nodes

Add variables to represent the two nodes to find the LCA for

Implement a function to find the LCA of the two nodes

Print the value of the LCA node

💡 Why This Matters

🌍 Real World

Finding common ancestors is useful in family tree applications, organizational charts, and network routing.

💼 Career

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

1

Create the Binary Tree Structure

Create a struct called TreeNode with an int val, and two pointers left and right. Then create the binary tree with these exact nodes and connections:
1 as root, 2 as root's left child, 3 as root's right child, 4 as left child of 2, and 5 as right child of 2.

DSA C++

// Define TreeNode struct and create the binary tree nodes
// Your code here

Hint

Start by defining the TreeNode struct with a constructor. Then create nodes and link them as described.

2

Set the Nodes to Find LCA For

Add two pointers called p and q and set them to point to the nodes with values 4 and 5 respectively in the tree.

DSA C++

#include 

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

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);

    // Set pointers p and q to nodes 4 and 5
    // Your code here

    return 0;
}

Hint

Use the tree structure to assign p and q to the correct nodes.

3

Implement the Lowest Common Ancestor Function

Write a function called lowestCommonAncestor that takes TreeNode* root, TreeNode* p, and TreeNode* q as parameters and returns the pointer to their lowest common ancestor node. Use recursion to check if root is nullptr, or equals p or q. Recursively search left and right subtrees, and return the correct ancestor node.

DSA C++

#include 

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) {
    // Implement the recursive LCA logic here
    // Your code here
}

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);

    TreeNode* p = root->left->left;  // Node with value 4
    TreeNode* q = root->left->right; // Node with value 5

    return 0;
}

Hint

Use recursion to find p and q in left and right subtrees. If both sides return non-null, current node is LCA.

4

Print the Lowest Common Ancestor Value

Call the lowestCommonAncestor function with root, p, and q. Store the result in a variable called ancestor. Then print the value of ancestor->val using std::cout.

DSA C++

#include 

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 || root == p || root == q) {
        return root;
    }
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left != nullptr && right != nullptr) {
        return root;
    }
    return left != nullptr ? left : right;
}

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);

    TreeNode* p = root->left->left;  // Node with value 4
    TreeNode* q = root->left->right; // Node with value 5

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

    return 0;
}

Hint

Call the function and print the val of the returned node.