Constructing a Binary Search Tree from Post Order traversal Efficiently.

Data Structure: Array,Binary Search Tree


Algorithm & Approach
1.As we have given Postorder Traversal we know last value will be root insert it in BST as Root.
2.While Iterating Over Array for each element (from as last position Obvious) compare root value
from next value in array so if
a. it is greater then root then insert it into right subtree of root Avg (logn),Worst O(N)
b. if next value is less then root then insert it into left subtree of root
3.End


Working Code:

#include
#include

typedef struct Tnode {
int data;
struct Tnode *left;
struct Tnode *right;
} Tnode;

#include
#include


/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
Tnode * newNode(int data)
{
Tnode * node = (Tnode *)
malloc(sizeof(Tnode ));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}


Tnode *constructBSTfrompostorder(Tnode *root,int a[],int n)
{
int i=0;
Tnode *t=NULL;
for(i=n-1;i>=0;i--)
{
t=root;
if(root==NULL)
{
root=newNode(a[i]);
continue;
}
while(root!=NULL)
{
if(a[i]>root->data)
{
if(root->right==NULL)
{
root->right=newNode(a[i]);
break;
}
root=root->right;
}
else
{
if(root->left==NULL)
{
root->left=newNode(a[i]);
break;
}
root=root->left;
}
}
root=t;
}
return root;
}

void postorder(Tnode *root)
{
if(root==NULL)
return;
postorder(root->left);
postorder(root->right);
printf("%d,",root->data);
}

int main(int argc, char** argv) {

Tnode *root=NULL;

/*root = createtreenode(15);

root->left = createtreenode(7);
root->right = createtreenode(25);

root->left->left = createtreenode(3);
root->left->right = createtreenode(10);

root->right->left = NULL;
root->right->right = createtreenode(50);

root->left->right->left = createtreenode(8);
root->left->right->right = createtreenode(12);

root->left->right->left->left = NULL;
root->left->right->left->right = createtreenode(9);

root->left->right->right->left = createtreenode(11);
root->left->right->right->right = createtreenode(14);

root->right->right->left = createtreenode(30);
root->right->right->right = createtreenode(55);

root->right->right->right->left = createtreenode(52);
root->right->right->right->right = NULL;*/

//postorder(root);

int a[]={3,9,8,11,14,12,10,7,30,52,55,50,25,15};
root=constructBSTfrompostorder(root,a,14);
postorder(root);
return (EXIT_SUCCESS);
}


Time Complexity O(NlogN) but in worst case it will take o(N^2) Time if we have given postorder
of right skewed tree
Space Complexity O(1)
Run Here http://ideone.com/3KMy7