fork download
copy 
  1. #include <stdio.h>
  2.  
  3. // Recursive function to find postorder traversal of binary tree
  4. // from its inorder and preorder sequence
  5. void printPostorder(int inorder[], int start, int end, 
  6.                     int preorder[], int *preIndex)
  7. {
  8.     // base case
  9.     if (start > end)
  10.         return;
  11.  
  12.     // The next element in preorder[] will be the root node of subtree formed
  13.     // by inorder[start, end]
  14.     int value = preorder[(*preIndex)++];
  15.  
  16.     // if current node is leaf node (no children)
  17.     if (start == end)
  18.     {
  19.         // print the value of root node and return
  20.         printf("%d ", value);
  21.         return;
  22.     }
  23.  
  24.     // search the index of root node in inorder[] to determine the
  25.     // boundary of left and right subtree of current root node
  26.     int i;
  27.     for (i = start; i <= end; i++) {
  28.         if (inorder[i] == value)
  29.             break;
  30.     }
  31.  
  32.     // recur for left subtree
  33.     printPostorder(inorder, start, i - 1, preorder, preIndex);
  34.  
  35.     // recur for right subtree
  36.     printPostorder(inorder, i + 1, end, preorder, preIndex);
  37.  
  38.     // print the value of root node
  39.     printf("%d ", value);
  40. }
  41.  
  42. // Find postorder traversal of a binary tree from its inorder and 
  43. // preorder sequence. This function assumes that the input is valid
  44. // i.e. given inorder and preorder sequence forms a binary tree
  45. void findPostorder(int inorder[], int preorder[], int n)
  46. {
  47.     // preIndex stores index of next unprocessed node in preorder sequence
  48.     int *preIndex;
  49.  
  50.     // root node is present at index 0 in preorder sequence
  51.     preIndex = 0;
  52.  
  53.     printf("Postorder Traversal is: ");
  54.     printPostorder(inorder, 0, n - 1, preorder, &preIndex);
  55. }
  56.  
  57. // main function
  58. int main(void)
  59. {
  60.     /* Consider below tree
  61.           1
  62.         /   \
  63.        /     \
  64.       2       3
  65.      /       / \
  66.     /       /   \
  67.    4       5     6
  68.           / \
  69.          /   \
  70.         7     8
  71.     */
  72.  
  73.     int inorder[]  = { 4, 2, 1, 7, 5, 8, 3, 6 };
  74.     int preorder[] = { 1, 2, 4, 3, 5, 7, 8, 6 };
  75.     int n = sizeof(inorder)/sizeof(inorder[0]);
  76.  
  77.     findPostorder(inorder, preorder, n);
  78.  
  79.     return 0;
  80. }
Success #stdin #stdout 0s 9424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Postorder Traversal is: 4 2 7 8 5 6 3 1
https://ideone.com/ELerfy
Find postorder traversal of a binary tree from its inorder and preorder sequence
language:
C (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!