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.

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. .

-6Postorder 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.

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

+2The 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.

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

Thanks

+1the 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.

+2Contribute 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;

}

0Following 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 );

}

-2thanks mate

+1For 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.

+4Hi,

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.

0but 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.

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

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

+1i 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 ?

+1How 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!

+1A 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.

+1A 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

+5Can 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?+1Sorry, I mean *first question!

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

0Pingback: Construct Binary Tree From Inorder and Preorder/Postorder Traversal | 口├人人│의 Blog

I have C# variant of this code available at

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

-1Hi 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?

-1With 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.

0The 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);

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

0Minor 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.

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

+1Here is a Java Version of the same problem

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

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

0it is too much complex!!!!

0here 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.

00Has this question been

reallyasked in an interview. It seems way too complicated. Am I the only one here thinking it is too much?0I 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.

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

+1Hi 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.

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

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

0So 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 ?

0Ok ^^^ See my tree here

-1May 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.

0In Java:

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

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

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

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

0The total time complexity is O(logN log N)

0Pingback: Amazon interview preparation | What I learn, I blog !

Pingback: leetcode: Construct Binary Tree from Inorder and Postorder/Preorder Traversal solution | 烟客旅人 sigmainfy

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.

0This 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;

}

0i 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;

}

0simpler approach using binary search for root-val

0simpler approach using binary search for root-val

0Your explanation is very helpful.

0answer 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

0public 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;

}

}

0this is helpfull for practice…..

00is it safe to remove these codes?

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

. in[] is only used in the function

.

0its 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..

+1