Introduction

The Lowest Common Ancestor (LCA) of two nodes in a binary tree is defined as the deepest node that has both nodes as descendants (where we allow a node to be a descendant of itself). For example, in a binary tree, given two nodes p and q, the LCA is the lowest (i.e., deepest) node that has both p and q as descendants.

Program Structure

The program will follow these steps:

1. Define a TreeNode structure to represent nodes in the binary tree.
2. Write a recursive function findLCA that finds the lowest common ancestor of two nodes.
3. Implement the main function to test the LCA functionality with a sample binary tree.

Code Implementation

// C++ program to find the lowest common ancestor of two nodes in a binary tree

#include <iostream>
using namespace std;

// Define the structure of a tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    // Constructor to initialize the tree node
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// Function to find the lowest common ancestor (LCA) of two nodes in a binary tree
TreeNode* findLCA(TreeNode* root, TreeNode* p, TreeNode* q) {
    // Base case: if the root is NULL or matches either p or q, return root
    if (root == NULL || root == p || root == q) {
        return root;
    }

    // Recursively find LCA in the left and right subtrees
    TreeNode* leftLCA = findLCA(root->left, p, q);
    TreeNode* rightLCA = findLCA(root->right, p, q);

    // If both leftLCA and rightLCA are non-null, the current root is the LCA
    if (leftLCA && rightLCA) {
        return root;
    }

    // Otherwise, return the non-null node (either from left or right subtree)
    return (leftLCA != NULL) ? leftLCA : rightLCA;
}

// Helper function to insert a new node into the binary tree (for testing purposes)
TreeNode* insert(TreeNode* node, int val) {
    if (node == NULL) return new TreeNode(val);  // If the tree is empty, create a new node

    // Otherwise, recursively insert the value into the left or right subtree
    if (val < node->val)
        node->left = insert(node->left, val);
    else
        node->right = insert(node->right, val);

    return node;
}

// Helper function to perform in-order traversal of the binary tree (for testing purposes)
void inOrderTraversal(TreeNode* root) {
    if (!root) return;

    inOrderTraversal(root->left);
    cout << root->val << " ";
    inOrderTraversal(root->right);
}

int main() {
    /* Sample Binary Tree:
              3
            /   \
           5     1
          / \   / \
         6   2 0   8
            / \
           7   4
    */

    // Creating the binary tree
    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);
    root->left->right->left = new TreeNode(7);
    root->left->right->right = new TreeNode(4);

    // Finding the LCA of nodes 5 and 1
    TreeNode* lca = findLCA(root, root->left, root->right);
    cout << "LCA of 5 and 1: " << lca->val << endl;

    // Finding the LCA of nodes 5 and 4
    lca = findLCA(root, root->left, root->left->right->right);
    cout << "LCA of 5 and 4: " << lca->val << endl;

    return 0;
}

Explanation

Let’s break down the program:

1. TreeNode structure: This structure represents a node in the binary tree. Each node stores a value val and pointers to its left and right children.
2. findLCA function: This is a recursive function that finds the lowest common ancestor (LCA) of two nodes p and q:
   • First, we check if the current node is null or matches either p or q. If so, the current node is returned as the LCA.
   • We then recursively check the left and right subtrees to find the LCA of the two nodes.
   • If both the left and right recursive calls return non-null values, it means p and q are located in different subtrees, and the current node is their LCA.
   • If only one of the recursive calls returns non-null, we return the non-null value, indicating that both p and q are located in the same subtree.
3. insert function: This helper function is used to insert nodes into the binary tree by comparing values. This is used for building the binary tree during testing.
4. inOrderTraversal function: This helper function performs an in-order traversal of the binary tree, printing the values in sorted order (optional for testing purposes).

How the Algorithm Works

The algorithm is based on recursively checking the left and right subtrees of the current node to find the LCA of the two given nodes:

• If both nodes are found in different subtrees, the current node is their LCA.
• If both nodes are found in the same subtree, the recursive function will return the LCA from that subtree.
• If one of the nodes is the root itself, then the root is the LCA.

Sample Output

If you run the above program with the provided sample binary tree, the output will be:

LCA of 5 and 1: 3
LCA of 5 and 4: 5

In the sample binary tree:

• The LCA of nodes 5 and 1 is 3, as both are in different subtrees of node 3.
• The LCA of nodes 5 and 4 is 5, since node 5 is an ancestor of node 4.

Conclusion

In this program, we implemented the algorithm to find the Lowest Common Ancestor (LCA) of two nodes in a binary tree using C++. The recursive approach efficiently finds the LCA by traversing the tree and checking where the two nodes exist relative to each other. The time complexity of this algorithm is O(N), where N is the number of nodes in the binary tree, as each node is visited once during the recursion.