C Program to Find the Common Ancestor and Path

This C Program Finds the Common Ancestor and Print the Path.

Here is source code of the C Program to Find the Common Ancestor and Print the Path. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C Program to Find the Common Ancestor and Print the Path
  3.  *
  4.  *                       10
  5.  *                       /  \                    
  6.  *                      7    15
  7.  *                     / \   / \
  8.  *                    6   8 12  18
  9.  *                   /     \
  10.  *                  5         9
  11.  *               (Given Binary tree) 
  12.  */
  13. #include <stdio.h>
  14. #include <stdlib.h>
  15.  
  16. struct btnode
  17. {
  18.     int value;
  19.     struct btnode *l;
  20.     struct btnode *r;
  21. };
  22.  
  23. typedef struct btnode N;
  24.  
  25. N* new(int);
  26. int count;
  27.  
  28. void create();
  29. void preorder(N *t);
  30. void ancestor(N *t);
  31. int search(N *t, int, int);
  32. void path(int, int, int);
  33.  
  34. N *root = NULL;
  35.  
  36. void main()
  37. {
  38.     int choice;
  39.  
  40.     create();
  41.     while (1)
  42.     {
  43.         printf("Enter the choice\n");
  44.         printf("1-Display : 2-path : 3-Exit\n");
  45.         scanf("%d", &choice);
  46.         switch (choice)
  47.         {
  48.         case 1:
  49.             printf("preorder display of tree elements\n");
  50.             preorder(root);
  51.             printf("\n");
  52.             break;
  53.         case 2:
  54.             ancestor(root);    
  55.             break;
  56.         case 3:
  57.             exit(0);
  58.         default:
  59.             printf("Enter the right choice\n");
  60.         }
  61.     }
  62. }
  63.  
  64. /* creating temporary node */
  65. N* new(int data)
  66. {
  67.     N* temp = (N*)malloc(sizeof(N));
  68.     temp->value = data;
  69.     temp->l = NULL;
  70.     temp->r = NULL;
  71.  
  72.     return(temp);
  73. }
  74.  
  75. /* Creating the binary search tree */
  76. void create()
  77. {
  78.     root = new(10);
  79.     root->l = new(7);
  80.     root->r = new(15);
  81.     root->l->l = new(6);
  82.     root->l->r = new(8);
  83.     root->r->l = new(12);
  84.     root->r->r = new(18);
  85.     root->r->r->r = new(20);
  86.     root->l->l->l = new(5);
  87.     root->l->r->r = new(9);
  88. }
  89.  
  90. /* To display the preorder traversal of the tree */
  91. void preorder(N *temp)
  92. {
  93.         printf("%d->", temp->value);
  94.         if (temp->l != NULL)
  95.             preorder(temp->l);
  96.         if (temp->r != NULL)
  97.             preorder(temp->r);
  98. }
  99.  
  100. /* to find common ancestor for given nodes */
  101. void ancestor(N *temp)
  102. {
  103.     int a, b, anc = 0;
  104.     count = 0;
  105.  
  106.     printf("enter two node values to find common ancestor\n");
  107.     scanf("%d", &a);
  108.     scanf("%d", &b);
  109.     count = search(root, a, b);
  110.     if (count  == 2)
  111.     {
  112.         while (temp->value != a && temp->value != b)
  113.         {
  114.             if ((temp->value > a)&&(temp->value > b))
  115.             { 
  116.                 anc = temp->value;
  117.                 temp = temp->l;
  118.             }
  119.             else if ((temp->value < a)&&(temp->value < b))
  120.             {
  121.                 anc = temp->value;
  122.                 temp = temp->r;
  123.             }
  124.             else if ((temp->value > a)&&(temp->value < b))
  125.             {
  126.                 anc = temp->value;            
  127.                 printf("anc = %d\n", anc);
  128.                 break;
  129.             }
  130.             else if ((temp->value < a)&&(temp->value > b))
  131.             {
  132.                 anc = temp->value;
  133.                 temp = temp->r;    
  134.             }
  135.             else
  136.             {
  137.                 printf("common ancestor = %d\n", anc);
  138.                 break;
  139.             }
  140.         }
  141.     path(anc, a, b);
  142.     }
  143.     else
  144.         printf("enter correct node values & do not enter root value\n");
  145. }
  146.  
  147. /* to find whether given nodes are present in tree or not */
  148. int search(N *temp, int a, int b)
  149. {
  150.     if ((temp->value  == a ||temp->value  == b)&& (root->value != a&&root->value != b))
  151.     {
  152.         count++;        
  153.     }
  154.     if (temp->l != NULL)
  155.         search(temp->l, a, b);
  156.     if (temp->r != NULL)
  157.         search(temp->r, a, b);
  158.     return count;
  159. }
  160.  
  161. /* to print the path ancestor to given nodes */
  162. void path(int anc, int c, int b)
  163. {
  164.     N *temp = NULL;
  165.     int i = 0, a[2];
  166.     a[0] = c;
  167.     a[1] = b;
  168.  
  169.     for (;i < 2;i++)
  170.     {
  171.         if (anc == root->value)    // If ancestor is root
  172.         {
  173.             temp = root;
  174.             while (1)
  175.             {
  176.                 printf("%d", temp->value);
  177.                 if (a[i] < temp->value)
  178.                     temp = temp->l;
  179.                 else if (a[i] > temp->value)
  180.                     temp = temp->r;
  181.                 else
  182.                 {
  183.                     if (a[i] == temp->value)
  184.                     {
  185.                         break;
  186.                     }
  187.                 }
  188.                 printf("->");
  189.             }
  190.             printf("\n");
  191.         }
  192.         else if (anc < root->value)    //If ancestor is less than the root value
  193.         {
  194.             temp = root;
  195.             while (temp != NULL)
  196.             {
  197.                 if (anc < temp->value)
  198.                     temp = temp->l;
  199.                 else if (anc > temp->value)
  200.                     temp = temp->r;
  201.                 else
  202.                 {
  203.                     while (1)
  204.                     {
  205.                         if (a[i] < temp->value)
  206.                         {
  207.                             printf("%d->", temp->value);
  208.                             temp = temp->l;
  209.                         }
  210.                         else if (a[i] > temp->value)
  211.                         {
  212.                             printf("%d->", temp->value);
  213.                             temp = temp->r;
  214.                         }
  215.                         else
  216.                         {
  217.                             printf("%d\n", temp->value);
  218.                             break;
  219.                         }
  220.                     }
  221.                 }
  222.             }
  223.         }
  224.         else //If ancestor greater than the root value
  225.         {
  226.             temp = root;
  227.             while (temp != NULL)
  228.             {
  229.                 if (anc > temp->value)
  230.                     temp = temp->r;
  231.                 else if (anc < temp->value)
  232.                     temp = temp->l;
  233.                 else
  234.                 {
  235.                     while (1)
  236.                     {
  237.                         if (a[i] < temp->value)
  238.                         {
  239.                             printf("%d->", temp->value);
  240.                             temp = temp->l;
  241.                         }
  242.                         else if (a[i] > temp->value)
  243.                         {
  244.                             printf("%d->", temp->value);
  245.                             temp = temp->r;
  246.                         }
  247.                         else
  248.                         {
  249.                             printf("%d\n", temp->value);
  250.                             break;
  251.                         }
  252.                     }
  253.                 }
  254.             }
  255.         }
  256.     }
  257. }

$ cc tree33.c
$ a.out
Enter the choice
1-Display : 2-path : 3-Exit
1
preorder display of tree elements
10->7->6->5->8->9->15->12->18->20
Enter the choice
1-Display : 2-path : 3-Exit
2
enter two node values to find common ancestor
6
8
anc = 7
7->6
7->8
Enter the choice
1-Display : 2-path : 3-Exit
2
enter two node values to find common ancestor
7
20
anc = 10
10->7
10->15->18->20
Enter the choice
1-Display : 2-path : 3-Exit
2
enter two node values to find common ancestor
12
20
anc = 15
15->12
15->18->20
Enter the choice
1-Display : 2-path : 3-Exit
2
enter two node values to find common ancestor
15
20
10->15
10->15->18->20
Enter the choice
1-Display : 2-path : 3-Exit
3

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.