Construct a Binary Tree from Inorder and PostOrder

June 23, 2019

Construct Binary Tree from given Postorder and Inorder traversals.

Example

InOrder = {41, 21, 51, 11, 61, 31, 71}
PostOrder = {41, 51, 21, 61, 71, 31, 11}
The root of the tree is the last element in the Postorder traversals. In the above example it is 1. 

The next step is to find the index position of 11 in the inorder. Suppose it is at position j. Now note the elements which are at the left of j as they will build left subtree and elements which are at the right of j will build right subtree. 

Now the structure of tree is:

Now we recur the process for both [41, 21, 51] which is left subtree and for [61, 31, 71] which right subtree.

inorder = {61, 31, 71} 

postorder = {61, 71, 31}……. Make the created tree as the right child of the root.

inorder = {41, 21, 51}

postorder = {41, 51, 21}…….Make the created tree as left child of root.

Consider, there are ‘a’ number of elements to the left of ‘j.’ These elements will construct the left subtree. Now, take first ‘a’ elements from the Postorder traversal, this will be the post order traversal for elements which are left to i. Likewise, if there are ‘b’ number of elements to the right of ‘j,’ then these elements will construct the right subtree. Now, take next ‘b’ elements, after ‘a’ elements from the postorder traversal, this will be the post order traversal for elements which are right to ‘j.’

The following binary tree is obtained:

Now considering the previous two steps, we will build the right and left subtree. These trees will be further linked to root right, and root left respectively.

The following binary tree is obtained:

Code

[code language=”css”]

/* Program to construct tree using inorder and postorder traversals */
#include <bits/stdc++.h>
using namespace std;

/* A binary tree node has data, a pointer to left child and a pointer to right child */
struct BTnode
{
int d1;
BTnode *left, *right;
};

// Create a new node
BTnode* newNode(int d1);

/* Find the index of value in array from start to end*/
int srch(int array[], int strt_index, int end_index, int val);

/* Recursive function to builds a binary tree of size l from Inorder and Postorder traversal. Initial values of inStrt and inEnd should
be 0 and l-1. For cases where inorder and postorder traversal do not form a tree, the function doesn’t do any error checking */
BTnode* buildTree(int inorder[], int postorder[], int inStrt, int inEnd, int* pIdx)
{
if (inStrt > inEnd)
return NULL;

/* Select present current node from Postorder traversal using postIndex and decrement postIndex (pIdx) */
BTnode* Node = newNode(postorder[*pIdx]);
(*pIdx)–;

/* If the current node has no children then return BTnode */
if (inStrt == inEnd)
return Node;

/* Else find the index of the current node in Inorder traversal */
int jIndex = srch(inorder, inStrt, inEnd, Node->d1);

/*With the help of index in Inorder traversal, construct right and left subtree */
Node->right = buildTree(inorder, postorder, jIndex + 1, inEnd, pIdx);
Node->left = buildTree(inorder, postorder, inStrt, jIndex – 1, pIdx);

return Node;
}

// The following function initializes index of root and calls buildTree()
BTnode* buildTree(int inorder[], int postorder[], int l)
{
int pIdx = l – 1;
return buildTree(inorder, postorder, 0, l – 1, &pIdx);
}

/* Function to find the index of the value in the array
The function assumes that value is postsent in inorder[] */
int srch(int array[], int strt_index, int end_index, int val)
{
int j;
for (j = strt_index; j <= end_index; j++) { if (array[j] == val) break; } return j; } /* Create new node */ BTnode* newNode(int d1) { BTnode* Node = (BTnode*)malloc(sizeof(BTnode)); /* Malloc allocates a block of uninitialized memory and returns a void pointer to the first byte of the allocated memory block if the allocation succeeds */ Node->d1 = d1;
Node->left = Node->right = NULL;
return (Node);
}

void preOT (BTnode* Node)
{
if (Node == NULL)
return;
printf("%d ", Node->d1);
preOT(Node->left);
preOT(Node->right);
}

// Driver code to test above functions
int main() /* a pre-defined function whose data type is integer */
{
int inorder[] = {41, 21, 51, 11, 61, 31, 71};
int postorder[] = {41, 51, 21, 61, 71, 31, 11};
int l = sizeof(inorder) / sizeof(inorder[0]);
BTnode* btnode= buildTree(inorder, postorder, l);
cout << "Preorder of the constructed tree : \n";
preOT(btnode);
return 0;
}

[/code]