C Programming Code Examples C > Beginners Lab Assignments Code Examples Find the Nearest Common Ancestor in the Given set of Nodes Find the Nearest Common Ancestor in the Given set of Nodes This C Program prints all the elements of Nth level in single line. #include <stdio.h> #include <stdlib.h> /* Structure of binary tree node */ struct btnode { int value; struct btnode *l; struct btnode *r; }; void createbinary(); node* add(int val); int height(node *); int nearest_common_ancestor(node*, int, int); typedef struct btnode node; node *root = NULL, *ptr; int main() { int c, x1, x2; createbinary(); printf("\nEnter nodes having common ancestor"); scanf("%d %d", &x1, &x2); c = nearestcommonancestor(root, x1, x2); if (c == -1) { printf("No common ancestor"); } else { printf("The common ancestor is %d", c); } } /* * constructing the following binary tree * 50 * / \ * 20 30 * / \ * 70 80 * / \ \ *10 40 60 */ void createbinary() { root = add(50); root->l = add(20); root->r = add(30); root->l->l = add(70); root->l->r = add(80); root->l->l->l = add(10); root->l->l->r = add(40); root->l->r->r = add(60); } /*Add node to binary tree */ node* add(int val) { ptr = (node*)malloc(sizeof(node)); if (ptr == NULL) { printf("Memory was not allocated"); return; } ptr->value = val; ptr->l = NULL; ptr->r = NULL; return ptr; } /*height of the binary tree */ int height(node *n) { int lheight, rheight; if (n != NULL) { lheight = height(n->l); rheight = height(n->r); if (lheight > rheight) return(lheight + 1); else return(rheight + 1); } } /*Finds the nearest common ancestor */ int nearestcommonancestor(node *temp, int x1, int x2) { int h, i, j, k; node *prev; /*If any one the inputted node is root then no common ancestor */ if (x1 == root->value || x2 == root->value) { return - 1; } h = height(root); for (i = 1;i < h;i++) { if (temp->l->value == x1 || temp->r->value == x1 || temp ->l->value == x2 || temp->r->value == x2) { prev = temp; for (j = 1, temp = root;j < h;j++) { if (temp != NULL) { if (temp->r->value == x2 || temp->r->value == x1 || temp->l->value == x1 || temp->l->value == x2) { /* * If the parent of x1 and parent of x2 are same then the value of parent is returned */ if (prev->value == temp->value) return prev->value; /* * otherwise from parents of two nodes is traversed upward if any node matches with other's node parent then that is * considered as common ancestor */ else for (k = 0, prev = temp;k < h;k++) { if (temp->l->value == prev->l->value) return temp->value; else temp = temp->l; } } } temp = temp->l; } } temp = temp->l; } }