Construct a binary tree from pre-order and in-order traversals given

 

Question

I came to know about this question from ihas1337code.com. The problem is to construct a normal binary tree from the given pre-order and in-order arrays.

For example,

say, you are given,

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

if you need to get a tree like this,

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

Source: http://www.ihas1337code.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html

How would you do that ? Just guess before going into above link

Approach

I came up with the approach. But feed-up with the recursion logic and broke my head with vectors & stacks. This is where the power of recursion is fully used. There are many problems like this which you must be used to get ready for interviews.The approach for this problem is like this,

• We know that the first node of the pre-order is definitely the root of the tree
• Subsequent nodes listed in the pre-order arrays are all roots of sub trees, coming with format left-right-root
• Also we know that, in-order traversal has left first, root and then right
• So, simply take a element in the pre-order array and search in the in-order array to get the indices. After you get the index, the left is the left sub tree, right is the right sub tree

For example, Consider the above input set.

The first iteration will be like,

_______7______
/ \

4 10 3 1                         11 8 2

So, detect 7 as the root.. search in the in-order array and find the index.. what you got is that, {4 10 3 1} are the nodes of the left sub tree and {11, 8, 2} are nodes of the right sub tree.

After you detect this, you need recursively do the same to in left and right lists to get the full tree constructed.

That is, the next root after seven is nothing but 10.. search for 10 in the left first.. having 10 as the root, 4 becomes the left and {3,1} becomes the right tree.

But how to do this approach ?

Approach – for implementation

The implementation of this approach is little bit tricky. Firstly, we should be very clear about what all we need replication for each tree creation. The following data is needed in each iteration,

• The root node!! its different for each sub-tree that we create
• the pre-order array movement and the in-order array movements.. we need to split the in-order arrays with root node found from pre-order array as the middle element.
• root->left and root->right should get the nodes which are processed in the future!! :(

After doing this exercise, i understood that, i need to restudy recursion again in a more clearer way :)

Recursive call of a function does the following things

• the arguments are put into a stack.. You can clearly see the arguments part of the call stack frame
• the local variables in the function are all replicated and if you return local variable value in the recursion.. it gets shared with the previous recursive function call in the stack.. :)

The local variables & return value based recursion is also known as tail recursion. We will see about this in detail separately.

We have to use tail recursion to successfully implement this code.

Code

struct BinaryTree 

{

    int data;

    BinaryTree* left;

    BinaryTree* right;

};

BinaryTree* newTreeNode(int data)

{

    BinaryTree* newNode = new BinaryTree;

    newNode->data = data;

    newNode->left = NULL;

    newNode->right = NULL;

    return newNode;

}

int getIndex(int* arr, int val, int size)

{

    for(int i=0; i<size;i++) {

        if(arr[i] == val) 

            return i;

    }

    return -1;

}

BinaryTree* create_bintree(int* parray, int* iarray, int size)

{

    if(size == 0) return NULL;

    int rootVal = parray[0];

    BinaryTree* root  = newTreeNode(rootVal);

    int newIdx = getIndex(iarray, rootVal, size);

    root->left = create_bintree(parray+1, iarray, newIdx);

    root->right = create_bintree(parray+newIdx+1, iarray+newIdx+1, size-newIdx-1);

    return root;            

}

void main()

{

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

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

    BinaryTree* tree = create_bintree(preorder, inorder, 8);

}

• We have taken some code logic from ihas1337code. But we don’t use mapIndex and offsets, as it complicates things and also adds a restriction to the element set
• Note that, elements should be unique!!.. Otherwise, this approach will never workout.. :)
• NEVER EVER TRY WITH vectors, stacks without recursion. It will screw up heavily!!
• every node gets a new tree Node with newTreeNode function inside create_bintree
• we do the tail recursion, parray+1 to get the root->left. and we will end this recursion only after we have also seen the right nodes in the tree. :)
• That is, when we reach 0 in root->left.. we check for root->right as well!!.. End condition is newIdx is 0 (i.e, size = 0)
• parray+1 and parray+newIdx+1 is simple logic
  • You get the newIdx from inorder array.. which is the middle element and the root.
  • 0 to newIdx-1 will be left and newIdx+1 to end will be the right
• iarray and iarray+newIdx+1 works uniformly with parray so that.. root->left gets only left side nodes and root->right gets only the right side nodes.
• size-newIdx-1 in this, –1 is just because the array index starts at 0. size-newIdx is the actual size of right half. that is, end – newIdx+1 is the size of the right side in all cases
• There are lots of invariant in this code!!.. and its not verified with all kinds of Input. Handle with care!! :)