fork download
copy 
  1. #include <iostream>
  2. /* A O(n) program for construction of  
  3. BST from postorder traversal */
  4. #include <bits/stdc++.h> 
  5. using namespace std; 
  6.  
  7. /* A binary tree node has data,  
  8. pointer to left child and a  
  9. pointer to right child */
  10. struct node 
  11. { 
  12.     int data; 
  13.     struct node *left, *right; 
  14. }; 
  15.  
  16. // A utility function to create a node 
  17. struct node* newNode (int data) 
  18. { 
  19.     struct node* temp = 
  20. (struct node *) malloc(sizeof(struct node)); 
  21.  
  22.     temp->data = data; 
  23.     temp->left = temp->right = NULL; 
  24.  
  25.     return temp; 
  26. } 
  27.  
  28. // A recursive function to construct  
  29. // BST from post[]. postIndex is used  
  30. // to keep track of index in post[]. 
  31. struct node* constructTreeUtil(int post[], int* postIndex, 
  32.                                int key, int min, int max,  
  33.                                int size) 
  34. { 
  35.     // Base case 
  36.     if (*postIndex < 0) 
  37.         return NULL; 
  38.  
  39.     struct node* root = NULL; 
  40.  
  41.     // If current element of post[] is  
  42.     // in range, then only it is part 
  43.     // of current subtree 
  44.     if (key > min && key < max) 
  45.     { 
  46.         // Allocate memory for root of this  
  47.         // subtree and decrement *postIndex 
  48.         root = newNode(key); 
  49.         *postIndex = *postIndex - 1; 
  50.  
  51.         if (*postIndex >= 0) 
  52.         { 
  53.  
  54.         // All nodes which are in range {key..max}  
  55.         // will go in right subtree, and first such  
  56.         // node will be root of right subtree. 
  57.         root->right = constructTreeUtil(post, postIndex,  
  58.                                         post[*postIndex], 
  59.                                         key, max, size ); 
  60.  
  61.         // Contruct the subtree under root 
  62.         // All nodes which are in range {min .. key}  
  63.         // will go in left subtree, and first such 
  64.         // node will be root of left subtree. 
  65.         root->left = constructTreeUtil(post, postIndex, 
  66.                                        post[*postIndex], 
  67.                                        min, key, size ); 
  68.         } 
  69.     } 
  70.     return root; 
  71. } 
  72.  
  73. // The main function to construct BST  
  74. // from given postorder traversal. 
  75. // This function mainly uses constructTreeUtil() 
  76. struct node *constructTree (int post[],  
  77.                             int size) 
  78. { 
  79.     int postIndex = size-1; 
  80.     return constructTreeUtil(post, &postIndex,  
  81.                              post[postIndex], 
  82.                              INT_MIN, INT_MAX, size); 
  83. } 
  84.  
  85. // A utility function to print 
  86. // inorder traversal of a Binary Tree 
  87. void printInorder (struct node* node) 
  88. { 
  89.     if (node == NULL) 
  90.         return; 
  91.     printInorder(node->left); 
  92.     cout << node->data << " "; 
  93.     printInorder(node->right); 
  94. } 
  95.  
  96. // Driver Code 
  97. int main () 
  98. { 
  99.     int post[] = {1, 7, 5, 50, 40, 10}; 
  100.     int size = sizeof(post) / sizeof(post[0]); 
  101.  
  102.     struct node *root = constructTree(post, size); 
  103.  
  104.     cout << "Inorder traversal of "
  105.         << "the constructed tree: \n"; 
  106.     printInorder(root); 
  107.  
  108.     return 0; 
  109. }
Success #stdin #stdout 0s 4504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Inorder traversal of the constructed tree: 
1 5 7 10 40 50
https://ideone.com/URDpMI
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

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!