#include <iostream>
/* A O(n) program for construction of
BST from postorder traversal */
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data,
pointer to left child and a
pointer to right child */
struct node
{
int data;
struct node *left, *right;
};
// A utility function to create a node
struct node* newNode (int data)
{
struct node* temp =
(struct node *) malloc(sizeof(struct node));
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// A recursive function to construct
// BST from post[]. postIndex is used
// to keep track of index in post[].
struct node* constructTreeUtil(int post[], int* postIndex,
int key, int min, int max,
int size)
{
// Base case
if (*postIndex < 0)
return NULL;
struct node* root = NULL;
// If current element of post[] is
// in range, then only it is part
// of current subtree
if (key > min && key < max)
{
// Allocate memory for root of this
// subtree and decrement *postIndex
root = newNode(key);
*postIndex = *postIndex - 1;
if (*postIndex >= 0)
{
// All nodes which are in range {key..max}
// will go in right subtree, and first such
// node will be root of right subtree.
root->right = constructTreeUtil(post, postIndex,
post[*postIndex],
key, max, size );
// Contruct the subtree under root
// All nodes which are in range {min .. key}
// will go in left subtree, and first such
// node will be root of left subtree.
root->left = constructTreeUtil(post, postIndex,
post[*postIndex],
min, key, size );
}
}
return root;
}
// The main function to construct BST
// from given postorder traversal.
// This function mainly uses constructTreeUtil()
struct node *constructTree (int post[],
int size)
{
int postIndex = size-1;
return constructTreeUtil(post, &postIndex,
post[postIndex],
INT_MIN, INT_MAX, size);
}
// A utility function to print
// inorder traversal of a Binary Tree
void printInorder (struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
cout << node->data << " ";
printInorder(node->right);
}
// Driver Code
int main ()
{
int post[] = {1, 7, 5, 50, 40, 10};
int size = sizeof(post) / sizeof(post[0]);
struct node *root = constructTree(post, size);
cout << "Inorder traversal of "
<< "the constructed tree: \n";
printInorder(root);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgovKiBBIE8obikgcHJvZ3JhbSBmb3IgY29uc3RydWN0aW9uIG9mICAKQlNUIGZyb20gcG9zdG9yZGVyIHRyYXZlcnNhbCAqLwojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4gCnVzaW5nIG5hbWVzcGFjZSBzdGQ7IAogIAovKiBBIGJpbmFyeSB0cmVlIG5vZGUgaGFzIGRhdGEsICAKcG9pbnRlciB0byBsZWZ0IGNoaWxkIGFuZCBhICAKcG9pbnRlciB0byByaWdodCBjaGlsZCAqLwpzdHJ1Y3Qgbm9kZSAKeyAKICAgIGludCBkYXRhOyAKICAgIHN0cnVjdCBub2RlICpsZWZ0LCAqcmlnaHQ7IAp9OyAKICAKLy8gQSB1dGlsaXR5IGZ1bmN0aW9uIHRvIGNyZWF0ZSBhIG5vZGUgCnN0cnVjdCBub2RlKiBuZXdOb2RlIChpbnQgZGF0YSkgCnsgCiAgICBzdHJ1Y3Qgbm9kZSogdGVtcCA9IAooc3RydWN0IG5vZGUgKikgbWFsbG9jKHNpemVvZihzdHJ1Y3Qgbm9kZSkpOyAKICAKICAgIHRlbXAtPmRhdGEgPSBkYXRhOyAKICAgIHRlbXAtPmxlZnQgPSB0ZW1wLT5yaWdodCA9IE5VTEw7IAogIAogICAgcmV0dXJuIHRlbXA7IAp9IAogIAovLyBBIHJlY3Vyc2l2ZSBmdW5jdGlvbiB0byBjb25zdHJ1Y3QgIAovLyBCU1QgZnJvbSBwb3N0W10uIHBvc3RJbmRleCBpcyB1c2VkICAKLy8gdG8ga2VlcCB0cmFjayBvZiBpbmRleCBpbiBwb3N0W10uIApzdHJ1Y3Qgbm9kZSogY29uc3RydWN0VHJlZVV0aWwoaW50IHBvc3RbXSwgaW50KiBwb3N0SW5kZXgsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaW50IGtleSwgaW50IG1pbiwgaW50IG1heCwgIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaW50IHNpemUpIAp7IAogICAgLy8gQmFzZSBjYXNlIAogICAgaWYgKCpwb3N0SW5kZXggPCAwKSAKICAgICAgICByZXR1cm4gTlVMTDsgCiAgCiAgICBzdHJ1Y3Qgbm9kZSogcm9vdCA9IE5VTEw7IAogIAogICAgLy8gSWYgY3VycmVudCBlbGVtZW50IG9mIHBvc3RbXSBpcyAgCiAgICAvLyBpbiByYW5nZSwgdGhlbiBvbmx5IGl0IGlzIHBhcnQgCiAgICAvLyBvZiBjdXJyZW50IHN1YnRyZWUgCiAgICBpZiAoa2V5ID4gbWluICYmIGtleSA8IG1heCkgCiAgICB7IAogICAgICAgIC8vIEFsbG9jYXRlIG1lbW9yeSBmb3Igcm9vdCBvZiB0aGlzICAKICAgICAgICAvLyBzdWJ0cmVlIGFuZCBkZWNyZW1lbnQgKnBvc3RJbmRleCAKICAgICAgICByb290ID0gbmV3Tm9kZShrZXkpOyAKICAgICAgICAqcG9zdEluZGV4ID0gKnBvc3RJbmRleCAtIDE7IAogIAogICAgICAgIGlmICgqcG9zdEluZGV4ID49IDApIAogICAgICAgIHsgCiAgCiAgICAgICAgLy8gQWxsIG5vZGVzIHdoaWNoIGFyZSBpbiByYW5nZSB7a2V5Li5tYXh9ICAKICAgICAgICAvLyB3aWxsIGdvIGluIHJpZ2h0IHN1YnRyZWUsIGFuZCBmaXJzdCBzdWNoICAKICAgICAgICAvLyBub2RlIHdpbGwgYmUgcm9vdCBvZiByaWdodCBzdWJ0cmVlLiAKICAgICAgICByb290LT5yaWdodCA9IGNvbnN0cnVjdFRyZWVVdGlsKHBvc3QsIHBvc3RJbmRleCwgIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcG9zdFsqcG9zdEluZGV4XSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBrZXksIG1heCwgc2l6ZSApOyAKICAKICAgICAgICAvLyBDb250cnVjdCB0aGUgc3VidHJlZSB1bmRlciByb290IAogICAgICAgIC8vIEFsbCBub2RlcyB3aGljaCBhcmUgaW4gcmFuZ2Uge21pbiAuLiBrZXl9ICAKICAgICAgICAvLyB3aWxsIGdvIGluIGxlZnQgc3VidHJlZSwgYW5kIGZpcnN0IHN1Y2ggCiAgICAgICAgLy8gbm9kZSB3aWxsIGJlIHJvb3Qgb2YgbGVmdCBzdWJ0cmVlLiAKICAgICAgICByb290LT5sZWZ0ID0gY29uc3RydWN0VHJlZVV0aWwocG9zdCwgcG9zdEluZGV4LCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcG9zdFsqcG9zdEluZGV4XSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbiwga2V5LCBzaXplICk7IAogICAgICAgIH0gCiAgICB9IAogICAgcmV0dXJuIHJvb3Q7IAp9IAogIAovLyBUaGUgbWFpbiBmdW5jdGlvbiB0byBjb25zdHJ1Y3QgQlNUICAKLy8gZnJvbSBnaXZlbiBwb3N0b3JkZXIgdHJhdmVyc2FsLiAKLy8gVGhpcyBmdW5jdGlvbiBtYWlubHkgdXNlcyBjb25zdHJ1Y3RUcmVlVXRpbCgpIApzdHJ1Y3Qgbm9kZSAqY29uc3RydWN0VHJlZSAoaW50IHBvc3RbXSwgIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgaW50IHNpemUpIAp7IAogICAgaW50IHBvc3RJbmRleCA9IHNpemUtMTsgCiAgICByZXR1cm4gY29uc3RydWN0VHJlZVV0aWwocG9zdCwgJnBvc3RJbmRleCwgIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgIHBvc3RbcG9zdEluZGV4XSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgSU5UX01JTiwgSU5UX01BWCwgc2l6ZSk7IAp9IAogIAovLyBBIHV0aWxpdHkgZnVuY3Rpb24gdG8gcHJpbnQgCi8vIGlub3JkZXIgdHJhdmVyc2FsIG9mIGEgQmluYXJ5IFRyZWUgCnZvaWQgcHJpbnRJbm9yZGVyIChzdHJ1Y3Qgbm9kZSogbm9kZSkgCnsgCiAgICBpZiAobm9kZSA9PSBOVUxMKSAKICAgICAgICByZXR1cm47IAogICAgcHJpbnRJbm9yZGVyKG5vZGUtPmxlZnQpOyAKICAgIGNvdXQgPDwgbm9kZS0+ZGF0YSA8PCAiICI7IAogICAgcHJpbnRJbm9yZGVyKG5vZGUtPnJpZ2h0KTsgCn0gCiAgCi8vIERyaXZlciBDb2RlIAppbnQgbWFpbiAoKSAKeyAKICAgIGludCBwb3N0W10gPSB7MSwgNywgNSwgNTAsIDQwLCAxMH07IAogICAgaW50IHNpemUgPSBzaXplb2YocG9zdCkgLyBzaXplb2YocG9zdFswXSk7IAogIAogICAgc3RydWN0IG5vZGUgKnJvb3QgPSBjb25zdHJ1Y3RUcmVlKHBvc3QsIHNpemUpOyAKICAKICAgIGNvdXQgPDwgIklub3JkZXIgdHJhdmVyc2FsIG9mICIKICAgICAgICA8PCAidGhlIGNvbnN0cnVjdGVkIHRyZWU6IFxuIjsgCiAgICBwcmludElub3JkZXIocm9vdCk7IAogIAogICAgcmV0dXJuIDA7IAp9IA==