C++ Program to Find the Lowest Common Ancestor in a Binary Tree

1. Introduction

The Lowest Common Ancestor (LCA) of two nodes n1 and n2 is defined as the lowest node in the tree that has both n1 and n2 as descendants. In this post, we will explore a C++ program to find the LCA in a binary tree.

2. Program Overview

Our approach involves a recursive traversal of the binary tree. As we traverse down from the root, if one of the nodes matches either n1 or n2, we return the node's pointer. Otherwise, we search in both the left and right subtrees. If both left and right subtree calls return non-NULL values, it indicates that the current node is the LCA. If only one subtree call returns non-NULL, then that return value is the LCA.

3. Code Program

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int val) : data(val), left(NULL), right(NULL) {}
};

Node* findLCA(Node* root, int n1, int n2) {
    if (!root) return NULL;

    // If either n1 or n2 matches with the root's key, report the presence
    if (root->data == n1 || root->data == n2) {
        return root;
    }

    // Look for n1 and n2 in left and right subtrees
    Node* left_lca = findLCA(root->left, n1, n2);
    Node* right_lca = findLCA(root->right, n1, n2);

    // If n1 and n2 are found in left and right subtrees of the current node, then it's the LCA
    if (left_lca && right_lca) return root;

    // Otherwise, check if the left subtree or right subtree is LCA
    return (left_lca != NULL) ? left_lca : right_lca;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    int n1 = 4, n2 = 5;
    Node* lca = findLCA(root, n1, n2);
    cout << "LCA of " << n1 << " and " << n2 << " is: " << lca->data << endl;

    return 0;
}

Output:

LCA of 4 and 5 is: 2

4. Explanation

The findLCA function recursively traverses the tree, and for each node, it checks if either of the input nodes matches with it. If it does, it returns the node. If not, it checks the left and right subtrees. If both left and right subtree calls have non-NULL return values, it means this current node is the LCA. Otherwise, we return whichever non-NULL value we get from the left or right subtree calls, indicating the LCA lies on that side.