Construct a binary Tree from its inorder and preorder traversal

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;



template<class PAYLOAD>
class node {
  public:
    node(PAYLOAD _p): p(_p) {}
    node* left;
    node*right;
    PAYLOAD p;
};

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

template<class PAYLOAD,size_t SIZE>
node<PAYLOAD>* reconstructTree(array<PAYLOAD,SIZE> preorder,uint& preIndex,uint instart, uint inend,
                               array<PAYLOAD,SIZE> inorder) {

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

    node<PAYLOAD>* p = new node<PAYLOAD>(preorder[preIndex++]);

    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;


}
template<class PAYLOAD>
void inOrderVisit(node<PAYLOAD>* r) {
    if(r) {
        inOrderVisit(r->left);
        printf(" %d ",r->p);
        inOrderVisit(r->right);
    }
}

template<class PAYLOAD>
void postOrderVisit(node<PAYLOAD>* r) {
    if(r) {
        inOrderVisit(r->left);
        printf(" %d ",r->p);
        inOrderVisit(r->right);
    }
}

template<class PAYLOAD>
void preOrderVisit(node<PAYLOAD>* r) {
    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:
exerciceBuildTree
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.

Be the first to leave a comment. Don’t be shy.

Join the Discussion

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>