This program demonstrates how to find the lowest common ancestor (LCA) of two nodes in a binary tree. The LCA is the deepest node that has both nodes as descendants.

Program Explanation

The program includes:

• Node Structure: Defines the structure of a binary tree node.
• LCA Function: Uses recursion to navigate the tree and find the LCA of two given nodes.
• Main Function: Sets up a sample tree, locates two nodes, and uses the LCA function to find their common ancestor.

Program Code

// Include necessary headers
#include <stdio.h>
#include <stdlib.h>

// Define the structure for tree nodes
typedef struct node {
    int data;
    struct node* left;
    struct node* right;
} Node;

// Function to create a new tree node
Node* newNode(int data) {
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

// Function to find LCA of n1 and n2
Node* findLCA(Node* root, int n1, int n2) {
    if (root == NULL) return NULL;

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

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

    // If both of the above calls return Non-NULL, then one key is present in one subtree and other is present in other,
    // So this node is the LCA
    if (left_lca && right_lca)  return root;

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

// Main function
int main() {
    // Let's create the binary tree shown in above diagram
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    
    Node* lca = findLCA(root, 4, 5);

    if (lca != NULL)
        printf("LCA(4, 5) = %d\\n", lca->data);
    else
        printf("Keys are not present in the tree\\n");

    return 0;
}
    

Key Components of the Program:

• Node Structure: Defines each node in the binary tree.
• newNode Function: Helper function to create a new node with provided data.
• findLCA Function: Recursively determines the LCA of two nodes. If both nodes are found in different branches of a node, that node is the LCA. If both are found in one branch, the function continues searching deeper in that branch.
• Main Function: Demonstrates the functionality by building a sample tree and finding the LCA of two nodes. It then prints the result.

This program efficiently determines the LCA using a simple recursive approach, navigating through the tree only once, making it both space and time-efficient for this task.