Program to Find Least Common Ancestor in a Binary Tree

  • Write a C program to find the least common Ancestor of two nodes.
  • Algorithm to find least common ancestor (LCA) of two nodes in a binary tree.

Given a binary tree and two nodes of given binary tree, we have to find Least Common Ancestor(LCA). The lowest common ancestor between nodes Node1 and Node1 is the lowest node in binary tree that has both Node1 and Node2 as descendants. A node is also a descendant of itself. In other word, LCA is the deepest node of binary tree which is ancestor of both nodes Node1 and Node2. Below is the structure of binary tree node. 

struct node {
    int data;
    struct node *left;
    struct node *right;
};
Algorithm to find Least Common Ancestor using recursion
Let "root" be the root of given binary tree and n1 and n2 be two given nodes.
  • If root is equal to either n1 or n2, then root is the LCA.
  • Recursively search for LCA in left and right sub tree.
  • If both of the recursive calls above returned non-NULL value, that means one of the node(either n1 or n2) is in left sub tree and another is in right sub tree. Hence root is the LCA.
  • If suppose only right sub tree returned non-Null value than both nodes are in right sub tree and right contains LCA.
  • If suppose only left sub tree returned non-Null value than both nodes are in left sub tree and left contains LCA.
Time Complexity : O(n)

C program to find least common ancestor in binary tree

#include 
#include 

#define TRUE 1
#define FALSE 0

struct node {
    int data;
    struct node *left;
    struct node *right;
};

struct node* getNewNode(int data) {
  /* dynamically allocate memory for a new node */ 
  struct node* newNode = (struct node*)malloc(sizeof(struct node));
 
  /* populate data in new Node */
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  
  return newNode;
}

/*
This function returns below tree
            7
           / \
         5    12
        / \    \
       4  50    8
      / \
     18  9
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(7);

    root->left = getNewNode(5);
    root->right = getNewNode(12);
    
    root->left->left = getNewNode(4);
    root->left->right = getNewNode(50);
    root->right->right = getNewNode(8);
 
    root->left->left->left = getNewNode(18);
    root->left->left->right = getNewNode(9);
    
    return root;
}

/* Returns the Least Common Ancestor of n1 and n2 */
struct node* findLCA(struct node* root, int n1, int n2) {

    /* Base Condition */
    if(root == NULL) {
        return NULL;
    }

    /* if root is equal to either n1 and n2 then root is LCA. */
    if(root->data == n1 || root->data == n2) {
        return root;
    } else {
        /* Search for LCA in left sub tree  */
        struct node  *left = findLCA(root->left , n1 , n2);
        /* Search for LCA in right sub tree  */
        struct node *right = findLCA(root->right , n1, n2);

        /* If one node is found in left sub tree and another in 
         right sub tree than root is Least common ancestor */
        if(left && right) {
            return root;
        }
        /* If both nodes are in left sub tree 
         that left is the lca  otherwise right */ 
        if(left) {
            return left;
        } else {
            return right;
        }
    }
}

int main() {
    struct node *root = generateBTree();    
    
    /* Printing Least Common Ancestors  */ 
    printf("Least Common Ancestor of 18 and 50: %d\n", 
        findLCA(root, 18, 50)->data);
    printf("Least Common Ancestor of 18 and 9: %d\n", 
        findLCA(root, 18, 9)->data);
    printf("Least Common Ancestor of 9 and 8: %d\n", 
        findLCA(root, 9, 8)->data);
    
    getchar();
    return 0; 
}
Output
Least Common Ancestor of 18 and 50: 5
Least Common Ancestor of 18 and 9: 4
Least Common Ancestor of 9 and 8: 7
Posted by
Labels: