C Programming Code Examples C > Beginners Lab Assignments Code Examples C Program to Find the Common Ancestor and Print the Path C Program to Find the Common Ancestor and Print the Path /* * * 10 * / \ * 7 15 * / \ / \ * 6 8 12 18 * / \ * 5 9 * (Given Binary tree) */ #include <stdio.h> #include <stdlib.h> struct btnode { int value; struct btnode *l; struct btnode *r; }; typedef struct btnode N; N* new(int); int count; void create(); void preorder(N *t); void ancestor(N *t); int search(N *t, int, int); void path(int, int, int); N *root = NULL; void main() { int choice; create(); while (1) { printf("Enter the choice\n"); printf("1-Display : 2-path : 3-Exit\n"); scanf("%d", &choice); switch (choice) { case 1: printf("preorder display of tree elements\n"); preorder(root); printf("\n"); break; case 2: ancestor(root); break; case 3: exit(0); default: printf("Enter the right choice\n"); } } } /* creating temporary node */ N* new(int data) { N* temp = (N*)malloc(sizeof(N)); temp->value = data; temp->l = NULL; temp->r = NULL; return(temp); } /* Creating the binary search tree */ void create() { root = new(10); root->l = new(7); root->r = new(15); root->l->l = new(6); root->l->r = new(8); root->r->l = new(12); root->r->r = new(18); root->r->r->r = new(20); root->l->l->l = new(5); root->l->r->r = new(9); } /* To display the preorder traversal of the tree */ void preorder(N *temp) { printf("%d->", temp->value); if (temp->l != NULL) preorder(temp->l); if (temp->r != NULL) preorder(temp->r); } /* to find common ancestor for given nodes */ void ancestor(N *temp) { int a, b, anc = 0; count = 0; printf("enter two node values to find common ancestor\n"); scanf("%d", &a); scanf("%d", &b); count = search(root, a, b); if (count == 2) { while (temp->value != a && temp->value != b) { if ((temp->value > a)&&(temp->value > b)) { anc = temp->value; temp = temp->l; } else if ((temp->value < a)&&(temp->value < b)) { anc = temp->value; temp = temp->r; } else if ((temp->value > a)&&(temp->value < b)) { anc = temp->value; printf("anc = %d\n", anc); break; } else if ((temp->value < a)&&(temp->value > b)) { anc = temp->value; temp = temp->r; } else { printf("common ancestor = %d\n", anc); break; } } path(anc, a, b); } else printf("enter correct node values & do not enter root value\n"); } /* to find whether given nodes are present in tree or not */ int search(N *temp, int a, int b) { if ((temp->value == a ||temp->value == b)&& (root->value != a&&root->value != b)) { count++; } if (temp->l != NULL) search(temp->l, a, b); if (temp->r != NULL) search(temp->r, a, b); return count; } /* to print the path ancestor to given nodes */ void path(int anc, int c, int b) { N *temp = NULL; int j = 0, a[2]; a[0] = c; a[1] = b; for (;j < 2;j++) { if (anc == root->value) // If ancestor is root { temp = root; while (1) { printf("%d", temp->value); if (a[j] < temp->value) temp = temp->l; else if (a[j] > temp->value) temp = temp->r; else { if (a[j] == temp->value) { break; } } printf("->"); } printf("\n"); } else if (anc < root->value) //If ancestor is less than the root value { temp = root; while (temp != NULL) { if (anc < temp->value) temp = temp->l; else if (anc > temp->value) temp = temp->r; else { while (1) { if (a[j] < temp->value) { printf("%d->", temp->value); temp = temp->l; } else if (a[j] > temp->value) { printf("%d->", temp->value); temp = temp->r; } else { printf("%d\n", temp->value); break; } } } } } else //If ancestor greater than the root value { temp = root; while (temp != NULL) { if (anc > temp->value) temp = temp->r; else if (anc < temp->value) temp = temp->l; else { while (1) { if (a[j] < temp->value) { printf("%d->", temp->value); temp = temp->l; } else if (a[j] > temp->value) { printf("%d->", temp->value); temp = temp->r; } else { printf("%d\n", temp->value); break; } } } } } } }
