Construct a Binary Tree from Inorder and Preorder

June 23, 2019

Given inorder and preorder tree traversals, construct the Binary tree.

Example

Given traversals:
 Preorder: 51, 24, 11, 36, 31, 41, 74, 63, 61, 71, 86
 Inorder: 11, 24, 31, 36, 41, 51, 61, 63, 71, 74, 86
1. In this series the first element that is ‘51’ of the pre order will be the root of the tree. 
2. Now here the search element is 51, which holds a central position of the tree, and all the numbers towards its left will form a left subtree and those to its right, will form a right subtree.
3. Next step is to find the index of 51 in the inorder traversal. The index found is 6. 
(Please note that, the numbers which are lesser that particular root number, will be written on the left hand side of that particular number and those of higher value will be written towards their right.)

The following binary tree is obtained:

In this picture Since 24 (2’nd number of preorder) is less than 51, hence it is written on the left of 51.

Then comes 11 which is lesser than 24, hence is written on the left of sub root 24.

Then comes 36, which is greater than its closest sub root 24, hence is written on the right of it.

Then comes 31, which is less that its closest sub root 36, therefore is written on its left.

Next number 41 will be written on the right of sub root 36 as it the next closest number which is greater than 36.

Then comes 74 which is greater than its closest root 51, hence will be written on the right of root 51.

63 is less than the sub root closest to it i.e. 74, hence will be written on its left hand side.

Next number is 61, and its closest sub root is 63 and since it is lesser than 63, hence will be written on its left.

Now the 2’nd last number of the series is 71 which is greater than its closest sub root 63, hence will be written on its right.

Last number of the series is 87, and as it is greater than its closest sub root 75, therefore will be written on its right.

Code

[code language=”css”]

/* The following program is to construct tree using inorder and preorder traversals */
#include
using namespace std;

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

// Find the index of value in array from start to end
int search (int arr[], int start_index, int end_index, int val)
{
int j;
for(j = start_index; j <= end_index; j++) { if (arr[j] == val) return j; } } /* New node creation */ BTnode *getNewNode(int val) { BTnode *new_BTnode = new BTnode; new_BTnode->val = val;
new_BTnode->left = NULL;
new_BTnode->right = NULL;
return new_BTnode;
}

// Inorder traversal of a tree
void inTraversal (BTnode *pointer)
{
if (pointer == NULL)
return;
else
{
inTraversal (pointer->left);
cout <val<<"t"; inTraversal(pointer->right);
}
}

// Constructing tree from its inorder and preorder traversals
BTnode* buildtree(int in[],int pre[],int in_strt, int in_end)
{
static int pre_index = 0;
if(in_strt > in_end)
return NULL;
/* Pick BTnode from Preorder traversal using pre_Index and increment pre_Index */
BTnode *tree_node = getNewNode(pre[pre_index++]);
// If this BTnode has no children then return the value */
if (in_strt == in_end)
return tree_node;

// Find the index of this node in the inorder array
int in_index = search(in, in_strt, in_end, tree_node->val);

// Build the left and right subtrees of this node
tree_node->left = buildtree (in, pre, in_strt, in_index-1);
tree_node->right = buildtree (in, pre, in_index+1, in_end);
return tree_node;
}
/* Program to test above functions */
int main() /* a pre-defined function whose data type is integer */
{
int in[] = {11, 24, 31, 36, 41, 51, 61, 63, 71, 74, 86};
int pre[] = {51, 24, 11, 36, 31, 41, 74, 63, 61, 71, 86};
int len = 11;
BTnode *btnode = buildtree (in, pre, 0, len – 1);
cout <<"Inorder traversal of the constructed tree is n";
inTraversal(btnode);
cout<<endl;
return 0;
}

[/code]