Construct a Binary Tree from its inorder and preorder

This article will investigate the problem of reconstructing a binary tree given its inorder and preorder traversal.

Let's say for instance that we have the following binary tree (see figure)

Binary Tree

which has the following in order and preorder traversal respectively.





Given IN and PRE how can we construct the original tree?

The key idea is to observe that the first element in  is the root of the tree and that the same element appears somewhere in , let's say at position . This means that in order traversal has processed k element before to process the root, meaning that the number of nodes of the left tree of the root is . Obviously, if the first  element belongs to the left subtree then all the others belongs to the right tree.

We will use this idea to write a recursive algorithm that builds the tree starting from its traversals. The algorithm works as follows:

1. Create a node with the first element of preorder visit
2. Find the index  of that element in the inorder list
3. recursively call the procedure on the subtree with root the next element not processed  in preorder and elements with indices in the range . This will be the left subtree.
4. recursively call the procedure on the subtree with root the next element not processed in preorder and elements with indices in the range . This will be the right subtree.
5.  The Base case is when the range contains only one element or less than zero. In the first case we simply return a node with the root element ( is a leaf) in the second case, we not recurse at all and return .

Construct a Binary Tree from its inorder and preorder -  CODE

#include <iostream>
#include<array>

using namespace std;

class node {
public:
node* left;
node*right;
};

int search(const ARRAY& a,int start, const int end, const PAYLOAD& p) {
while(start <=end)
if(a[start]==p)
return start;
else
start++;
}

printf("- %d, %d,%d\n",preIndex,instart,inend);
if(instart > inend)
return nullptr;

if(instart == inend)
return p;

int idx = search(inorder,instart,inend,p->p);
printf("Left %d ",idx);
p->left = reconstructTree(preorder,preIndex,instart,idx-1,inorder);
printf("rght %d ",idx);
p->right = reconstructTree(preorder,preIndex,idx+1,inend,inorder );

return p;

}
if(r) {
inOrderVisit(r->left);
printf(" %d ",r->p);
inOrderVisit(r->right);
}
}

if(r) {
inOrderVisit(r->left);
printf(" %d ",r->p);
inOrderVisit(r->right);
}
}

if(r) {
printf(" %d ",r->p);
preOrderVisit(r->left);
preOrderVisit(r->right);
}
}

#define size (8)
int main() {

array<uint,size> preorder = {1,2,4,5,3,7,6,8};
array<uint,size> inorder  = {4,2,5,1,6,7,3,8};

uint preIdx =0;
auto n = reconstructTree<uint>(preorder,preIdx,0,size-1,inorder);
inOrderVisit(n);
printf("\n");
preOrderVisit(n);
return 0;
}



As an example of execution see the following image:

Each node has a label composed of three part:

1.  is the index (in the preorder traversal) of the root of the current subtree.
2.  is search range in the inorder traversal. (all the node of the subtree that we are building lies in that interval)
3. k is the index at which we found  inside elements of inorder which index is between 

At each step of recursion, we increase a shared variable  and we are basically asking the following question: At which index inside inorder traversal we found ? Having that info, we can recurse left using  as new root and  as indices for inorder search on the left subtree and  and  as root and indices on the right subtree.

Worst case complexity is  when the tree is a list. The two traversal are one the reverse of the other and each recursive call will decrease the search range by one only. The search number  requires  lookup operations yielding to a total of  lookups.