Construct BST from Postorder

Given postorder traversal of a Binary Search Tree, you need to construct a BST from postorder traversal. The output will be inorder traversal of the constructed BST.

 

Example 1:

Input:
6
1 7 5 50 40 10

Output:
1 5 7 10 40 50

Explanation:
Testcase 1: The BST for the given post order traversal is:
                                
                      10
                     /  \
                    5    40
                   / \     \
                  1   7     50


Thus the inorder traversal of BST is: 1 5 7 10 40 50.

 

c++ implementation:

struct Node* insert(struct Node* node, int key)
{   struct Node*tt= new Node(key);
    /* If the tree is empty, return a new node */
    if (node == NULL) return tt;

    /* Otherwise, recur down the tree */
    if (key < node->data)
        node->left = insert(node->left, key);
    else if (key > node->data)
        node->right = insert(node->right, key); 

    /* return the (unchanged) node pointer */
    return node;
}

Node *constructTree (int post[], int size)
{  sort(post,post+size);   Node*head=NULL;
   for(int i=0;i<size;i++)
   {  
       head= insert(head, post[i]);
   }
   return head;
}

Time Complexity: O(n) 

space Complexity: O(n)