## Construct Binary Tree From Inorder and Preorder/Postorder Traversal

April 20, 2011 in binary tree

Given preorder and inorder traversal of a tree, construct the binary tree.

**Hint:**

A good way to attempt this question is to work backwards. Approach this question by drawing a binary tree, then list down its preorder and inorder traversal. As most binary tree problems, you want to solve this recursively.

**About Duplicates:**

In this solution, we will assume that duplicates are not allowed in the binary tree. Why?

Consider the following case:

preorder = {7, 7} inorder = {7, 7}

We can construct the following trees which are both perfectly valid solutions.

7 7 /or\ 7 7

Clearly, there would be ambiguity in constructing the tree if duplicates were allowed.

**Solution:**

Let us look at this example tree.

_______7______ / \ __10__ ___2 / \ / 4 3 _8 \ / 1 11

The preorder and inorder traversals for the binary tree above is:

preorder = {7,10,4,3,1,2,8,11} inorder = {4,10,3,1,7,11,8,2}

The crucial observation to this problem is *the tree’s root always coincides with the first element in preorder traversal*. This must be true because in preorder traversal you always traverse the root node before its children. The root node’s value appear to be **7** from the binary tree above.

We easily find that **7** appears as the 4^{th} index in the inorder sequence. (Notice that earlier we assumed that duplicates are not allowed in the tree, so there would be no ambiguity). For inorder traversal, we visit the left subtree first, then root node, and followed by the right subtree. Therefore, all elements left of **7** must be in the left subtree and all elements to the right must be in the right subtree.

We see a clear recursive pattern from the above observation. After creating the root node (**7**), we construct its left and right subtree from inorder traversal of {4, 10, 3, 1} and {11, 8, 2} respectively. We also need its corresponding preorder traversal which could be found in a similar fashion. If you remember, preorder traversal follows the sequence of root node, left subtree and followed by right subtree. Therefore, the left and right subtree’s postorder traversal must be {10, 4, 3, 1} and {2, 8, 11} respectively. Since the left and right subtree are binary trees in their own right, we can solve recursively!

We left out some details on how we search the root value’s index in the inorder sequence. How about a simple *linear search*? If we assume that the constructed binary tree is always balanced, then we can guarantee the run time complexity to be O(*N* log *N*), where *N* is the number of nodes. However, this is not necessarily the case and the constructed binary tree can be skewed to the left/right, which has the worst complexity of O(*N*^{2}).

A more efficient way is to eliminate the search by using an efficient look-up mechanism such as *hash table*. By hashing an element’s value to its corresponding index in the inorder sequence, we can do look-ups in constant time. Now, we need only O(*N*) time to construct the tree, which theoretically is the most efficient way.

For illustration purpose, the below code uses a simple array for table look-up, which is restricted to elements of 0 to 255 only. You should be able to extend it easily to use a hash table.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | const int MAX = 256; // a fast lookup for inorder's element -> index // binary tree's element must be in the range of [0, MAX-1] int mapIndex[MAX]; void mapToIndices(int inorder[], int n) { for (int i = 0; i < n; i++) { assert(0 <= inorder[i] && inorder[i] <= MAX-1); mapIndex[inorder[i]] = i; } } // precondition: mapToIndices must be called before entry Node *buildInorderPreorder(int in[], int pre[], int n, int offset) { assert(n >= 0); if (n == 0) return NULL; int rootVal = pre[0]; int i = mapIndex[rootVal]-offset; // the divider's index Node *root = new Node(rootVal); root->left = buildInorderPreorder(in, pre+1, i, offset); root->right = buildInorderPreorder(in+i+1, pre+i+1, n-i-1, offset+i+1); return root; } |

Now, if we are given* inorder and postorder* traversal, can we construct the binary tree?

The answer is yes, using very similar approach as above. Below is the code:

1 2 3 4 5 6 7 8 9 10 11 | // precondition: mapToIndices must be called before entry Node *buildInorderPostorder(int in[], int post[], int n, int offset) { assert(n >= 0); if (n == 0) return NULL; int rootVal = post[n-1]; int i = mapIndex[rootVal]-offset; // the divider's index Node *root = new Node(rootVal); root->left = buildInorderPostorder(in, post, i, offset); root->right = buildInorderPostorder(in+i+1, post+i, n-i-1, offset+i+1); return root; } |

**Further Thoughts:**

- If we are given
*preorder and postorder*traversal, can we construct the binary tree? Why or why not? - Given
*preorder, inorder, and postorder*traversal, how can you verify if these traversals are referring to the*exact same*binary tree? - Remember from my earlier post: Serialization/Deserialization of a Binary Tree? It is trivial to see this as an alternative method to serialize/deserialize a binary tree.

speeddy said on April 20, 2011

The post order could already recover the whole tree. While need inorder and post order together?

In your Serialization/Deserialization of a Binary Tree, you also just use post order to recover. .

-31337c0d3r said on April 20, 2011

Postorder alone could not construct the binary tree, unless it is a sorted binary tree (BST). My example above purposely used an unordered binary tree to avoid assumption that the binary tree is sorted. To serialize/deserialize using preorder/postorder alone you have to store extra sentinels along with the nodes’ value.

+9Kyle said on April 20, 2011

Can you clarify what exactly the offset and divider’s index are and their importance to the algorithm?

01337c0d3r said on April 20, 2011

The divider’s index is just the index of the root value in the inorder sequence.

The offset is used for the mapIndex[] array only. mapIndex[] array maps a value to index in the inorder array. However, when we separate the tree into its right subtree, the corresponding inorder subarray is passed in as in+i+1. This alters the original index of the array and it won’t work if we use mapIndex[] directly. Therefore, we need to record the offset from the original array.

+1Sudhanshu said on May 25, 2011

What is the offset initially be called with. Can you pls provide the call method parameters.

Thanks

0Pushparajan said on May 26, 2011

the initial offset should be zero.. the offset+i+1 is done since in+i+1 is done. Since we start with in+i+1, our indexes should be -(i+1).

For implementation without offset and mapIndex check here

But obviously, its slower than map version.

0raullen said on June 9, 2011

Contribute my code :

#include

#include

using namespace std;

struct node{

node* left;

node* right;

int data;

};

node* root;

void buildtree(node *b, int left_selected ,int* preorder, int* inorder){

int preorder_1[8] = {-1,-1,-1,-1,-1,-1,-1,-1};

int preorder_2[8] = {-1,-1,-1,-1,-1,-1,-1,-1};

int inorder_1[8] = {-1,-1,-1,-1,-1,-1,-1,-1};

int inorder_2[8] = {-1,-1,-1,-1,-1,-1,-1,-1};

int i, j, k1, k2;

//insert preorder[0];

if(b==NULL){

root = b = new node;

b->data = preorder[0];

b->left = b->right = NULL;

}

else{

node* tmp = new node;

tmp->data = preorder[0];

tmp->left = tmp->right = NULL;

if(left_selected)

b->left = tmp;

else

b->right = tmp;

b = tmp;

}

i = 0;

while(inorder[i] != preorder[0]){

inorder_1[i] = inorder[i];

i++;

}

i++;

j = 0;

while(inorder[i] != -1 ){

inorder_2[j] = inorder[i];

j++;

i++;

}

i = j = k1 = k2 = 0;

while(preorder[i] != -1 ){

i++;

int flag = false;

j = 0;

while(inorder_1[j] != -1 ){

if (inorder_1[j] == preorder[i]){

flag = true;

break;

}

j++;

}

if(flag){

preorder_1[k1] = preorder[i];

k1++;

}

else{

preorder_2[k2] = preorder[i];

k2++;

}

}

if(preorder_1[0] != -1)

buildtree(b, 1, preorder_1, inorder_1);

if(preorder_2[0] != -1)

buildtree(b, 0, preorder_2, inorder_2);

}

int main()

{

root = NULL;

int preorder[] = {7,10,4,3,1,2,8,11,-1};

int inorder[] = {4,10,3,1,7,11,8,2,-1};

buildtree(root, 1 ,preorder, inorder);

return 1;

}

0Henian said on June 15, 2011

Following is my codes. The same algorithm as introduced here.

template

void binaryTree::constructTreeFromPreorderInorderSets()

{

vector preorderSet;

vector inorderSet;

cout <> numberNodes;

cout << "Input preorder set one by one:" << endl;

T tmp;

for( int i = 0 ; i > tmp;

preorderSet.push_back( tmp );

}

cout << "Input inorder set one by one:" << endl;

for( int i = 0 ; i > tmp;

inorderSet.push_back( tmp );

}

int p = 0;

bool * nodeAdded = new bool[ numberNodes ];

for( int i = 0 ; i < numberNodes; i ++ ) nodeAdded[i] = false;

constructTreeRecurselyInorderPreorder( 0, numberNodes-1, p, root, preorderSet, inorderSet, nodeAdded, numberNodes );

}

template

void binaryTree::constructTreeRecurselyInorderPreorder( int begin, int end, int & p, treeNode * & subroot, const vector & preorderSet, const vector & inorderSet, bool * nodeAdded, const int & numberNodes )

{

if( begin > end ) return;

subroot = new treeNode( preorderSet[p], NULL, NULL );

int i,j; //position of A[p] at set B (suppose A is preorder set, B is inorder set)

//we must compare in each small segment: begin-end

for( i = begin ; i = numberNodes )

{

cerr << "Error:" << "preorderSet["<<p<<"]=" << preorderSet[p]<leftChild, preorderSet, inorderSet, nodeAdded, numberNodes );

constructTreeRecurselyInorderPreorder( j+1, end, p, subroot->rightChild, preorderSet, inorderSet, nodeAdded, numberNodes );

}

-2Pratik said on March 15, 2012

thanks mate

+1Henian said on June 15, 2011

For problem 1 “If we are given preorder and postorder traversal, can we construct the binary tree? Why or why not?”, I think the answer is no, right? I think there will be problem with leaves whose parent has only 1 child because in such case such leaf can be either left or right child.

+3lipingwu said on August 6, 2011

Hi,

I have different answer however. Following is my explanation. How do you think?

1. Given preorder and postorder traversal, we can still construct the binary tree. For the preorder, the first is root node, followed by nodes of the left subtree, followed by nodes of the right subtree. For the postorder, the last is root node, in front of which they are the nodes of the right subtree, in front of which they are the nodes of the left subtree. So, the second last element in the postorder will be the root node of the right subtree. Finding the position of the root node of the right subtree in the preorder, then the preorder can be partitioned into three parts: root node, followed by the nodes of the left subtree, followed by the nodes of the right subtree. The later two parts can be constructed into left subtree and right subtree respectively and recursively. For the post order, it can also be partitioned into three parts by coounting the number of nodes in each part. In fact, in recursion function, we always reconstruct the right subtree first and then left subtree, and decrease the index for postorder by one in each recursion. Then the index for the postorder will always point to the right element.

//Then, Therefore, we can see that we can still construct the binary tree given the preorder and postorder

//traversal.

-1rajeeb said on February 7, 2014

but i am having some different answer.we can only construct full binary tree(all nodes except last leaf level two child nodes)and the strictly binary tree(if n leaf node then 2n-1 total nubers of nodes) if the preorder and post order is given.because for all the other trees post and pre order may be same but not the inorder is same.So the resultant tree may yield different structures for all binary tree except full binary and strictly binary tree.

+2waseem said on November 5, 2014

please sir give me one example to make a tree…..by both pre or post

0lipingwu said on August 8, 2011

Henian, forget my previous post. You are right. I agree with you now.

+1alekya said on July 21, 2012

i want to represent in an array and it should perform the operations of inorder ,preorder,postorder with out using linked list and with out traversal it should be in an level wise.how can i ?

+1Henian said on June 15, 2011

How to answer the second question please: Given preorder, inorder, and postorder traversal, how can you verify if these traversals are referring to the exact same binary tree?

Thanks!

+1lipingwu said on August 6, 2011

A preorder, inorder or postorder traversal can come from more than two different binary trees. For example, given an inorder traversal {4, 2, 5, 1, 6, 3, 7}, any element can be viewed as the root node of the binary tree, generating different binary trees. So I don’t think we can verify if these traversals are referring to the exact same binary tree.

0Spring Coder said on June 17, 2011

A little pythonic.

def maketree(preorder, inorder):

global tree

if len(preorder) == 0:

return None

`root = preorder[0]`

ind = inorder.index(root)

linorder = filter(lambda x: inorder.index(x) ind, inorder)

lpreorder = filter(lambda x: x in linorder, preorder)

rpreorder = filter(lambda x: x in rinorder, preorder)

tree[root] = [maketree(lpreorder, linorder), maketree(rpreorder, rinorder)]

return root

`tree = {}`

pO = [7,10,4,3,1,2,8,11]

iO = [4,10,3,1,7,11,8,2]

maketree(pO, iO)

print tree

</code

+4Abby said on June 17, 2011

Can you give a logic answer for the second question?

If we are given preorder and postorder traversal, can we construct the binary tree? Why or why not?+1Abby said on June 17, 2011

Sorry, I mean *first question!

-1Anand said on June 17, 2011

http://anandtechblog.blogspot.com/2011/06/construct-given-tree-from-pre-order-and.html

0tryingout said on August 3, 2011

I have C# variant of this code available at

http://tryingout101.blogspot.com/2011/08/deserializing-binary-tree-from-inorder.html

0lipingwu said on August 7, 2011

Hi 1337,

For the second problem in further thought, I don’t think we can verify if these traversals are referring to the exact same binary tree.

A preorder, inorder or postorder traversal can come from more than two different binary trees.

For example, given an inorder traversal {4, 2, 5, 1, 6, 3, 7}, any element can be viewed as the root node of the binary tree, generating different binary trees.

How do you think?

0moonus said on September 5, 2011

With preorder and inorder, we first construct a tree. Then we use postorder to print this tree, and compare the printout with our given postorder array. This way, we can verify the answer.

0moonus said on September 5, 2011

The code is a little hard to understand. I have tried to copy it and run the given code myself to get a better understanding. I am not sure how many of you have done this, but after my analyse, the code to build tree from inorder and preorder will give us the tree differently, which the last node 11 is the right node of 8. Can anyone verify this?

const int TREE_SIZE = 8;

int in_order[TREE_SIZE] = {4, 10, 3, 1, 7, 8, 11, 2};

int pre_order[TREE_SIZE] = {7, 10, 4, 3, 1, 2, 8, 11};

const int MAX = 256;

int mapIndex[MAX];

for (int i = 0; i < TREE_SIZE; i++)

{

mapIndex[in_order[i]] = i;

}

buildInorderPreorder( in_order, pre_order, TREE_SIZE, 0, mapIndex);

0moonus said on September 5, 2011

Sorry, my bad, I apparently have used the wrong array of inorder.

0Aaron said on November 17, 2011

Minor bug: The method cannot deal with duplicate bcs the mapping will only record the last occurrence of number, the latter 2 in your example tree.

-21337c0d3r said on November 17, 2011

In my post, I already mentioned: “In this solution, we will assume that duplicates are not allowed in the binary tree.”

+1Braga said on December 21, 2011

Here is a Java Version of the same problem

http://www.technicalypto.com/2011/12/reconstruct-binary-tree-given-its.html

0SHawn said on January 18, 2012

Actually you can simplify it by remove argument in[ ]. Since you never actually use it in function.

0krishna priya said on January 27, 2012

it is too much complex!!!!

0Attila said on January 28, 2012

here is a slightly simpler to understand version of your solution:

Node *buildInorderPreorder(int mapIndex[], int pre[], int lo, int hi) {

if (hi left = buildInorderPreorder(mapIndex, pre+1, lo, i);

root->right = buildInorderPreorder(mapIndex, pre+i-lo+1, i+1, hi);

return root;

}

You dont really need the array in, because the only role of in is to determine the dividers index i, but i is more efficiently determined with the hash table mapIndex.

Instead of n and offset, I think the algorithm is simpler to understand in terms of indices lo and hi. In each recursion step, the range (lo, hi) is divided into (lo,i) and (i+1,hi). The recursion ends when the range is empty.

0Attila said on January 28, 2012

0reader said on February 27, 2012

Has this question been

reallyasked in an interview. It seems way too complicated. Am I the only one here thinking it is too much?0reader said on February 27, 2012

I mean even your code is not perfect.You use

as a parameter in the methods and do pointer arithmetic passing it as argument in subsequent calls but this parameter is actually redudant and not used in the code.This makes the code not readable which IMO it is something important in an interview.

+1Lindsey Fang said on March 10, 2014

I think 1337 should delete the parameter “int[] in” in the recursion. in[] has no use after you got mapIndex array

+1UnderMonkey said on April 12, 2012

Hi 1337c0d3r, I found in your buildInorderPreorder, the use of the divider’s index and offset is a little complicated. Can I instead use the common (start, end) pair to specify the range? The only thing that need to be taken care of is when to increment the root’s index in the pre_order[]. The following is my code with the same algorithm. Please let me know if you find anything wrong.

0jgan said on August 4, 2012

Hi 1337c0d3r, if duplicates are allowed, is it possible to build a binary tree from Inorder and Preorder/Postorder Traversal ?

0harish k said on November 13, 2012

is it possible to reconstruct a unique tree from give anyone of three traversal order?

0Inder said on November 23, 2012

So according to you

1) Search for ROOT

2) Then on Left and Right sub tree apply Binery Search Tree

Then the resulting tree would be :-

7

/ \

10 11

/ \

4 8

/ /

3 2

/

1

Right ?

0Inder said on November 23, 2012

Ok ^^^ See my tree here

-1perfumes said on January 2, 2013

May I simply say what a relief to uncover someone that truly understands what they’re talking about online. You certainly realize how to bring an issue to light and make it important. More and more people really need to read this and understand this side of your story. I was surprised that you’re not more popular given that you certainly have the gift.

0Ozan Tabak said on January 4, 2013

In Java:

(Recursive methods can be converted to in-place for further optimization)

+1Ozan Tabak said on January 4, 2013

Here’s in place version of the same java implementation of mine:

0Inder said on January 11, 2013

I found a tutorial here http://bloggerplugnplay.blogspot.in/2012/11/construction-of-binary-tree-from.html

0aad said on January 21, 2013

For the linear search, when the tree is perfectly balanced, the time should be n/2 rather than logn, right?

0TK said on October 18, 2014

The total time complexity is O(logN log N)

0Vicky said on May 14, 2013

Good day! I simply would like to give a massive thumbs up for the truly amazing information you

have here for this subject post. I shall be coming back on the weblog for more

soon.

0Deepak Singhal said on May 23, 2013

This code contains a run-time error, modified code is as follows..

int mapIndex[20];

void mapToIndices()

{

for (int i = 0; i < cnt; i++)

{

mapIndex[inorder[i]] = i;

}

}

// precondition: mapToIndices must be called before entry

Node buildInorderPreorder(int in[], int pre[], int n)

{

if (n 1)

{

root->left = buildInorderPreorder(in, pre+1, i);

root->right = buildInorderPreorder(in+i+1, pre+i+1, n-i-1);

}

return root;

}

Node buildInorderPostorder(int in[], int post[], int n)

{

if (n 1)

{

root->left = buildInorderPostorder(in, post, i);

root->right = buildInorderPostorder(in+i+1, post+i, n-i-1);

}

return root;

}

0Abhi Ram said on July 1, 2013

i did this in no time and is a much easier way of solving this problem

`#include`

using namespace std;

struct node

{

int data;

node *left,*right;

}*root;

`int inorder[]={4,10,3,1,7,11,8,2};`

int preorder[]={7,10,4,3,1,2,8,11};

int j=0;

`node* check(int a,int b)`

{

node *temp;

temp=new node;

if(a>b)

return NULL;

for(int i=a;idata=preorder[j++];

temp->left=check(a,i-1);

temp->right=check(i+1,b);

}

return temp;

}

`void display(node *sr)`

{

if(sr!=NULL)

{

cout<data<left);

display(sr->right);

}

return;

}

`int main()`

{

root=NULL;

root=check(0,7);

cout<<"The preorder traversal: ";

display(root);

system("pause");

return 0;

}

0fafdu said on July 4, 2013

simpler approach using binary search for root-val

0fafdu said on July 4, 2013

simpler approach using binary search for root-val

0vasantunt said on August 3, 2013

Your explanation is very helpful.

0Amit said on September 2, 2013

answer to: if three orders are given, find whether they beling to the same tree of not

First confirm if all the orders have the same number of elements.

Using inorder and postrder, we can find preorder and after finding each element, we can compare it with the given preorder. If it does not match at any instant, it means the orders are not of a single BT

0Mao Zhao said on September 12, 2013

public class Solution {

int pre;

public TreeNode buildTree(int[] preorder, int[] inorder) {

// Start typing your Java solution below

// DO NOT write main() function

pre = 0;

if(preorder.length == 0){return null;}

return build(preorder, inorder, 0, preorder.length-1);

}

public TreeNode build(int[] preorder, int[] inorder, int left, int right){

if(left > right){

return null;

}

//if(pre > preorder.length){

// return null;

//}

int key = preorder[pre];

pre++;

TreeNode tn = new TreeNode(key);

int i = 0;

for(i = left; i <= right; i++){

if(inorder[i] == key){break;}

}

tn.left = build(preorder, inorder, left, i-1);

tn.right = build(preorder, inorder, i+1, right);

return tn;

}

}

0manisha said on October 22, 2013

this is helpfull for practice…..

0Jim Liu said on November 27, 2013

0sunshiwu said on April 14, 2014

is it safe to remove these codes?

0Yunsong Wu said on May 28, 2014

I agree with @SHawn, and some people else that in[] is not needed in the function

. in[] is only used in the function

.

0ANUPAM CHANDA said on November 20, 2014

its wrong in the explanation == “Therefore, the left and right subtree’s postorder traversal must be {10, 4, 3, 1} and {2, 8, 11} respectively. ”

but it should be== “Therefore, the left and right subtree’s preorder traversal must be {10, 4, 3, 1} and {2, 8, 11} respectively. ”

just look at the tree..

0