C Program to Find Maximum Distance Between Two Nodes in a Binary Tree

«
»
This C Program finds nodes which are at maximum distance in binary tree.

Here is source code of the C Program find nodes which are at maximum distance in binary tree. 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 Nodes which are at Maximum Distance in Binary Tree
  3.  */
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6.  
  7. struct btnode
  8. {
  9.     int value;
  10.     struct btnode *r,*l;
  11. } *root = NULL, *temp = NULL;
  12.  
  13. void create();
  14. void insert();
  15. void add(struct btnode *t);
  16. void maxdistance(struct btnode *t);
  17.  
  18. int count = 0, max = 0, v[100] = {0}, z = 0, max2, max1[100] = {0};
  19.  
  20. void main()
  21. {
  22.     int ch, i;
  23.  
  24.     printf("Program to find nodes at maximum distance");
  25.     printf("\n  OPERATIONS ----"); 
  26.     printf("\n1] Insert ");
  27.     printf("\n2] Display nodes ");
  28.     printf("\n3] Exit ");    
  29.     while (1)
  30.     {                        
  31.         printf("\nEnter your choice : ");
  32.         scanf("%d", &ch);
  33.         switch (ch)
  34.         {
  35.         case 1:    
  36.             insert();
  37.             break;
  38.         case 2:    
  39.             max = 0;
  40.             count = 0;
  41.             maxdistance(root);
  42.         for (i = 1; i < z; i++)
  43.         {
  44.             max2 = max1[0];
  45.             if (max2 < max1[i])
  46.                 max2 = max1[i];
  47.         }
  48.         printf("Maximum distance nodes \nNodes\t Distance "); 
  49.         for (i = 0; i < z; i++)
  50.         {
  51.             if (max2 == max1[i])
  52.                 printf("\n %d\t  %d ",v[i],max2);        
  53.         }
  54.         break;
  55.         case 3: 
  56.             exit(0);
  57.         default :     
  58.             printf("Wrong choice, Please enter correct choice  ");
  59.             break;    
  60.         }
  61.     }
  62. }
  63.  
  64. /* To create a new node with the data from the user */
  65. void create()
  66. {
  67.     int data;
  68.  
  69.     printf("Enter the data of node : ");
  70.     scanf("%d", &data);
  71.     temp = (struct btnode* ) malloc(1*(sizeof(struct btnode)));
  72.     temp->value = data;
  73.     temp->l = temp->r = NULL;
  74. }
  75.  
  76. /* To check for root node and then create it */
  77. void insert()
  78. {
  79.     create();
  80.  
  81.     if (root == NULL)
  82.         root = temp;
  83.     else
  84.         add(root);
  85. }
  86.  
  87. /* Search for the appropriate position to insert the new node */
  88. void add(struct btnode *t)
  89. {
  90.     if ((temp->value > t->value) && (t->r!=NULL))    /* value more than root node value insert at right */
  91.         add(t->r);
  92.     else if ((temp->value > t->value) && (t->r==NULL))
  93.         t->r = temp;
  94.     else if ((temp->value < t->value) && (t->l!=NULL))   /* value less than root node value insert at left */
  95.         add(t->l);
  96.     else if ((temp->value < t->value) && (t->l==NULL))
  97.         t->l = temp;
  98. }
  99.  
  100. /* Function to find the max distance nodes */
  101. void maxdistance(struct btnode *t)
  102. {
  103.     if (t->l!=NULL)
  104.     {
  105.         count++;            /* to count the number of nodes in between root and leaf */
  106.         maxdistance(t->l);
  107.     }
  108.     if (max < count)
  109.         max = count;
  110.     if (max == count)
  111.     {
  112.         max1[z] = max;
  113.         v[z] = t->value;
  114.         z++;
  115.     }
  116.     if (t->r != NULL)
  117.     {
  118.         count++;        
  119.         maxdistance(t->r);
  120.     }
  121.     count--;
  122. }

$ cc tree19.c
$ a.out
Program to find nodes at maximum distance
OPERATIONS ----
   1] Insert 
   2] Display nodes 
   3] Exit 
   Enter your choice : 1
   Enter the data of node : 50
 
   Enter your choice : 1
   Enter the data of node : 30
 
   Enter your choice : 1
   Enter the data of node : 20
 
   Enter your choice : 1
   Enter the data of node : 40
 
   Enter your choice : 1
   Enter the data of node : 35
 
   Enter your choice : 1
   Enter the data of node : 100
 
   Enter your choice : 1
   Enter the data of node : 70
 
   Enter your choice : 1
   Enter the data of node : 120
 
   Enter your choice : 1
   Enter the data of node : 140
 
   Enter your choice : 2
   Maximum distance nodes 
   Nodes     Distance 
    35      3 
    140      3 
 
 
            50
            /\
           /  \
         30    100
         / \   / \
       20  40 70 120
           /       \
          35       140
 
    Enter your choice : 3
 
 
   $ ./a.out
 
   Program to find nodes at maximum distance
      OPERATIONS ----
   1] Insert 
   2] Display nodes 
   3] Exit 
   Enter your choice : 1
   Enter the data of node : 40
 
   Enter your choice : 1
   Enter the data of node : 20
 
   Enter your choice : 1
   Enter the data of node : 60
 
   Enter your choice : 1
   Enter the data of node : 10
 
   Enter your choice : 1
   Enter the data of node : 30
 
   Enter your choice : 1
   Enter the data of node : 80
 
   Enter your choice : 1
   Enter the data of node : 90
 
   Enter your choice : 2
   Maximum distance nodes 
      Nodes     Distance 
       90     3 
   Enter your choice : 3
 
 
 
            40
            /\
           /  \
         20    60
         / \    \
       10  30   80
                  \
                  90

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
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 & technical discussions at Telegram SanfoundryClasses.