C Program to Find Two Longest Distance Nodes using Inorder Traversal

This C Program find 2 nodes with longest distance and display using inorder traversal.

Here is source code of the C Program to find 2 nodes with longest distance and display using inorder traversal. 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 2 Nodes with Longest Distance and Display 
  3.  * using Inorder Traversal
  4.  *             40
  5.  *             /\
  6.  *           20 60
  7.  *           /\  \
  8.  *         10 30  80
  9.  *                 \
  10.  *                  90
  11.  */
  12. #include <stdio.h>
  13. #include <stdlib.h>
  14.  
  15. struct btnode
  16. {
  17.    int value;
  18.    struct btnode *left, *right;
  19. };
  20. typedef struct btnode node;
  21.  
  22. /* function prototypes */
  23. void insert(node *, node *);
  24. void inorder(node *);
  25. int  height(node *);
  26.  
  27. node *temp, *root = NULL;
  28.  
  29. void main()
  30. {
  31.     node *new = NULL ;
  32.     int num  = 1;
  33.  
  34.     printf("Enter the elements of the tree(enter 0 to exit)\n");
  35.     while (1)
  36.     {
  37.         scanf("%d",  &num);
  38.         if (num == 0)
  39.             break;
  40.         new  =  malloc(sizeof(node));
  41.         new->left  =  new->right  =  NULL;
  42.         new->value  =  num;
  43.         if (root  == NULL)
  44.             root  =  new;
  45.         else
  46.         {
  47.             insert(new, root);
  48.         }
  49.     }
  50.     printf("elements in a tree in inorder are\n");
  51.     inorder(root);
  52.     height(root);
  53. }
  54.  
  55. /* displaying nodes of a tree using inorder */
  56. void inorder(node *root)
  57. {
  58.     if (root != NULL)
  59.     {
  60.         inorder(root->left);
  61.         printf("%d -> ", root->value);
  62.         inorder(root->right);
  63.     }
  64. }
  65.  
  66. /* inserting nodes into a tree */
  67. void insert(node * new , node *root)
  68. {
  69.     if (new->value>root->value)
  70.     {
  71.         if (root->right  == NULL)
  72.             root->right  =  new;
  73.         else
  74.             insert(new, root->right);
  75.     }
  76.     if (new->value<root->value)
  77.     {
  78.         if (root->left  == NULL)
  79.             root->left = new;
  80.         else
  81.             insert(new, root->left);
  82.     }
  83. }
  84.  
  85. /* to find the longest path */
  86. int height(node *temp)
  87. {
  88.     temp = root;
  89.  
  90.     if (temp  == NULL)
  91.         printf("tree is empty\n");
  92.     else
  93.     {
  94.         printf("\nlongest path is\n");
  95.         while (temp->left != NULL)
  96.         {
  97.             if (temp->left == NULL)
  98.                 temp = temp->right;
  99.             else
  100.                 temp = temp->left;
  101.         }
  102.         printf("%d ->", temp->value);
  103.         temp = root;
  104.         while (temp->right != NULL)
  105.         {
  106.               if (temp->right  == NULL)
  107.                 temp = temp->left;
  108.             else
  109.                 temp = temp->right;
  110.         }
  111.         printf(" %d", temp->value);
  112.     }
  113. }

$ cc tree40.c
$ a.out
Enter the elements of the tree(enter 0 to exit)
40
20
30
50
60
80
90
0
elements in a tree in inorder are
20 -> 30 -> 40 -> 50 -> 60 -> 80 -> 90
longest path is
20 -> 90

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.