C Program to Construct Binary Tree from Postorder and Inorder

This C Program Build Binary Tree if Inorder or Postorder Traversal as Input.

Here is source code of the C Program to Build Binary Tree if Inorder or Postorder Traversal as Input. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C  Program to Build Binary Tree if Inorder or Postorder Traversal as Input
  3.  *
  4.  *                     40
  5.  *                    /  \
  6.  *                   20   60
  7.  *                  /  \   \
  8.  *                 10  30   80
  9.  *                           \
  10.  *                           90    
  11.  *             (Given Binary Search 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. }*root = NULL, *temp = NULL;
  22.  
  23. typedef struct btnode N;
  24. void insert();
  25. N* bt(int arr[],int,int);
  26. N* new(int);
  27. void inorder(N *t);
  28. void create();
  29. void search(N *t);
  30. void preorder(N *t);
  31. void postorder(N *t);
  32.  
  33. void main()
  34. {
  35.     int ch, i, n;
  36.     int arr[] = {10, 20, 30, 40, 60, 80, 90};
  37.     n = sizeof(arr) / sizeof(arr[0]);
  38.  
  39.     printf("\n1- Inorder\n");
  40.     printf("2 - postorder\n");
  41.     printf("\nEnter choice : ");
  42.     scanf("%d", &ch);
  43.     switch (ch)
  44.     {
  45.     case 1:
  46.         root = bt(arr, 0, n-1); 
  47.         printf("Given inorder traversal as input\n");
  48.         for (i = 0;i< = 6;i++)
  49.             printf("%d->", arr[i]);
  50.         printf("\npreorder traversal of tree\n");
  51.         preorder(root);
  52.         printf("\ninorder traversal of tree\n");
  53.         inorder(root);
  54.         printf("\npostorder traversal of tree\n");
  55.         postorder(root);
  56.         break;
  57.     case 2:
  58.         insert();
  59.         printf("\npreorder traversal of tree\n");
  60.         preorder(root);
  61.         printf("\nInorder traversal of tree\n");
  62.         inorder(root);
  63.         printf("\npostorder traversal of tree\n");
  64.         postorder(root);
  65.         break;
  66.         default:printf("enter correct choice");
  67.     }
  68. }
  69.  
  70. /* To create a new node */
  71. N* new(int val)
  72. {
  73.     N* node = (N*)malloc(sizeof(N));
  74.  
  75.     node->value = val;
  76.     node->l = NULL;
  77.     node->r  =  NULL;
  78.     return node;
  79. }
  80.  
  81. /* To create a balanced binary search tree */
  82. N* bt(int arr[], int first, int last)
  83. {
  84.     int mid;
  85.  
  86.     N* root = (N*)malloc(sizeof(N));
  87.     if (first > last)
  88.         return NULL;
  89.     mid = (first + last) / 2;
  90.     root = new(arr[mid]);
  91.     root->l = bt(arr, first, mid - 1);
  92.     root->r = bt(arr, mid + 1, last);
  93.     return root;
  94. }
  95.  
  96. /* Insert a node in the tree */
  97. void insert()
  98. {
  99.     int arr1[] = {10, 30, 20, 90, 80, 60, 40}, i;
  100.  
  101.     printf("Given post order traversal array\n");
  102.     for (i = 0;i <= 6;i++)
  103.     {
  104.         printf("%d->", arr1[i]);
  105.      }
  106.     for (i = 6;i >= 0;i--) 
  107.     {
  108.         create(arr1[i]);
  109.         if (root =  = NULL)
  110.             root = temp;
  111.         else
  112.             search(root);
  113.     }
  114. }
  115.  
  116. /*Create a node */
  117. void create(int data)
  118. {
  119.     temp = (N *)malloc(1*sizeof(N));
  120.  
  121.     temp->value = data;
  122.     temp->l = temp->r = NULL;
  123. }
  124.  
  125. /* Search for the appropriate position to insert the new node */
  126. void search(N *t)
  127. {
  128.     if ((temp->value>t->value)&&(t->r != NULL))
  129.         search(t->r);
  130.     else if ((temp->value>t->value)&&(t->r  == NULL))
  131.         t->r = temp;
  132.     else if ((temp->value<t->value)&&(t->l != NULL))
  133.         search(t->l);
  134.     else if ((temp->value<t->value)&&(t->l == NULL))
  135.         t->l = temp;
  136. }
  137.  
  138. /* to display inorder of tree */
  139. void inorder(N *t)
  140. {
  141.     if (t->l != NULL)
  142.         inorder(t->l);
  143.     printf("%d->", t->value);
  144.     if (t->r != NULL)
  145.         inorder(t->r);
  146. }
  147.  
  148. /* to display preorder traversal of tree */
  149. void preorder(N *t) 
  150. {
  151.     printf("%d->", t->value);
  152.     if (t->l != NULL)
  153.         inorder(t->l);
  154.     if (t->r != NULL)
  155.         inorder(t->r);
  156. }
  157.  
  158. /* to display postorder traversal of tree */
  159. void postorder(N *t) 
  160. {
  161.     if (t->l != NULL)
  162.         inorder(t->l);
  163.     if (t->r != NULL)
  164.         inorder(t->r);
  165.     printf("%d->", t->value);
  166. }

$ cc trees.c
$ a.out
 
1- Inorder
2 - postorder
Enter choice : 1
Given inorder traversal as input
10->20->30->40->60->80->90
preorder traversal of tree
40->10->20->30->60->80->90
inorder traversal of tree
10->20->30->40->60->80->90
postorder traversal of tree
10->20->30->60->80->90->40
 
$ a.out
1 - Inorder
2 - postorder
Enter choice : 2
Given post order traversal array
10->30->20->90->80->60->40
preorder traversal of tree
40->10->20->30->60->80->90
Inorder traversal of tree
10->20->30->40->60->80->90
postorder traversal of tree
10->20->30->60->80->90->40

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.