How to code Binary Search Tree from given PreOrder and PostOrder Traversals

So, the question is pretty similar to a puzzle. But first of all, we need to understand our problem and what information we can get from it.

Let me give you a simple example,

PreOrder[] = {1, 2, 4, 5, 3, 6, 7}

PostOrder[] = {4, 5, 2, 6, 7, 3, 1}

Here, the root, right now, is 1 because it should have preordered while creating PreOrder traversal by its definition. Also, it will come last in PostOrder traversal.

Next, the thing you can observe is the person on the right of 1 is its Left Child in PreOrder, i.e. 2. Similarly, 3must be the Right Child of 1, called Root right now.

So we can easily find Root, Left Child, and Right Child immediately from a given sequence. Next thing we want to see this Left Child in PostOrder and Right Child in PreOrder. Then we will get a partitioned order traversals something like this:-

PreOrder[] = {1, |2, 4, 5,| 3, 6, 7}

PostOrder[] = {4, 5, 2,| 6, 7, 3,| 1}

From here, we get our motivation for something like a recursion. So now we have to code a function which will help us in propagating this recursion. Now we need to decide what parameters our function needs to take to propagate this recursion. It needs both of the partitioned arrays of traversals, and that's it. That's all we need. As C doesn’t allow us to slice arrays so we will operate using indexes. This is fine.

But if we are proceeding through recursion, we need to think about termination also. Here are the possible termination cases that we can think of.

Termination 1(When 1 element remains in the array): So if your program has functioned correctly, then we are all set, but the recursive nature will kill everything. So, this condition will arrive when only one element remains. Then we will create a node, but it left child, and the right child needs to be set as zero, and our program terminates.

Termination 2(When two elements remain in the arrays): As we are coding a Binary Search Tree so, we can assume that Left Child always comes first. And here also our program terminates.

Below is the full program and a working demo, but I highly suggest you come here only here after spending almost a week on it, otherwise go and search some other stuff for sharpening your skills.

typedef struct Tree_Node
{
 int data;
 struct Tree_Node* Left_Child;
 struct Tree_Node* Right_Child;
}Tree_Node;
void Make(Tree_Node **imp, int *PreO, int *PostO, int pr_st, int pr_fin, int pt_st, int pt_fin)
{
 printf(“Call no %d\n”, i++);
 if( pr_st==pr_fin ) //Termination Case 1 when single element remains
 {
 Tree_Node*t;
 t = (Tree_Node*)malloc(sizeof(Tree_Node));
 t->data = PreO[pr_st];
 t->Left_Child = t->Right_Child = NULL;
 *imp = t; //Actual Linking
 return;
 }
 else if( pr_st+2 == pr_fin ) //Termination Case 2 when three element remains
 {
 Tree_Node *t, *tlc, *trc;
 t = (Tree_Node*)malloc(sizeof(Tree_Node));
 tlc = (Tree_Node*)malloc(sizeof(Tree_Node));
 trc = (Tree_Node*)malloc(sizeof(Tree_Node));
 t->data = PreO[pr_st];
tlc->data = PreO[pr_st+1];
 trc->data = PreO[pr_st+2];
tlc->Right_Child = tlc->Left_Child = NULL;
 trc->Right_Child = trc->Left_Child = NULL;
t->Left_Child = tlc;
 t->Right_Child = trc;
 (*imp) = t; //Actual Linking
 return;
 }
 else if( pr_st+1 == pr_fin ) //Termination Case 3 when two element remains,
 {
 Tree_Node*t, *t1;
 t = (Tree_Node*)malloc(sizeof(Tree_Node));
 t1 = (Tree_Node*)malloc(sizeof(Tree_Node));
t->Right_Child = t->Left_Child = NULL;
 t1->Right_Child = t1->Left_Child = NULL;
t->data = PreO[pr_st];
 t1->data = PreO[pr_fin];
 t->Left_Child = t1;
(*imp) = t; //Actual Linking
 return;
 }
 else //No termination, further Propagation
 {
 Tree_Node*t;
 t = (Tree_Node*)malloc(sizeof(Tree_Node));
 t->data = PreO[pr_st];
 t->Left_Child = t->Right_Child = NULL;
 (*imp) = t; //Actual Linking
int lc_p = Give_Me_Index( PreO[pr_st+1], PostO); //finding the position of left child in PostOrder
 int rc_p = Give_Me_Index( PostO[pt_fin-1], PreO); //finding the position of right child in PreOrder
Make(&t->Left_Child, PreO, PostO, pr_st+1, rc_p-1, pt_st, lc_p);
 Make(&t->Right_Child, PreO, PostO, rc_p, pr_fin, lc_p+1, pt_fin-1);
 return;
 }
}
int Give_Me_Index(int num, int A[])
{
 int p = 0;
 while( A[p]!=num ){ p++; } //go ahead until you find it
 return p;
}
void Inorder(Tree_Node* x)
{
 if(x)
 {
 if(x->Left_Child) Inorder(x->Left_Child);
 printf(“..%d..\n”, x->data); //data in the middle
 if(x->Right_Child) Inorder(x->Right_Child);
 }
}
int main()
{
 int n = 11;
 Tree_Node* Root;
int PreO[] = {1, 2, 4, 3, 5, 6, 13, 8, 7, 11, 12};
 int PostO[] = {2, 5, 13, 8, 6, 3, 11, 12, 7, 4, 1};
Make(&Root, &PreO, &PostO, 0, n-1, 0, n-1);
 Inorder(Root);
 Delete(Root);
 return 0;
}

Below is a demo for the above-explained program

Printing Inorder traversal of the tree in the end

Thank you for reading this article, and I hope this helps otherwise Google and Youtube are there for you always.

Happy Learning (: — — — :)

/* Ping me up for any queries akcgjc007@gmail.com */