Rebuild a binary tree from Inorder and Preorder traversals

This is a well known problem where given any two traversals of a tree  such as inorder & preorder or inorder & postorder or inorder & levelorder traversals we need to rebuild the tree.

The following procedure demonstrates on how to rebuild tree from given inorder and preorder traversals of a binary tree:

  • Preorder traversal visits Node, left subtree, right subtree recursively
  • Inorder traversal visits left subtree, node, right subtree recursively
  • Since we know that the first node in Preorder is its root, we can easily locate the root node in the inorder traversal and hence we can obtain left subtree and right subtree from the inorder traversal recursively

Consider the following example:

Preorder Traversal:    1    2    4    8    9    10    11    5    3    6    7

Inorder Traversal:       8    4    10    9    11    2    5    1    6    3    7

Iteration 1:

Root – {1}

Left Subtree – {8,4,10,9,11,2,5}

Right Subtree – {6,3,7}

Iteration 2:

Root – {2}

Left Subtree – {8,4,10,9,11}

Right Subtree – {5}

Root – {3}

Left Subtree – {6}

Right Subtree – {7}

Iteration 3:

Root – {2}

Left Subtree – {8,4,10,9,11}

Right Subtree – {5}

Root – {3}

Left Subtree – {6}

Right Subtree – {7}

Root – {4}

Left Subtree – {8}

Right Subtree – {10,9,11}

Done Done

Iteration 4:

Root – {2}

Left Subtree – {8,4,10,9,11}

Right Subtree – {5}

Root – {3}

Left Subtree – {6}

Right Subtree – {7}

Root – {4}

Left Subtree – {8}

Right Subtree – {10,9,11}

Done Done
Done R – {9}

Left ST – {10}

Right ST-{11}

Done Done

The following are the two versions of programming solutions even though both are based on above mentioned algorithm:

  • Creating left preorder, left inorder, right preorder, right inorder lists at every iteration to construct tree
  • Passing index of preorder and inorder traversals and using the same input list to construct tree

Implementation for Node, Tree, BinaryTree can be obtained from my previous post.

Creating left preorder, left inorder, right preorder, right inorder lists at every iteration to construct  tree

In this version we create left preorder, left inorder, right preorder, right inorder sublists and construct tree recursively. This follows procedure as described above diagrammatically.

package ds;

import java.util.ArrayList;
import java.util.List;

public class InorderPreorder
{
    public InorderPreorder()
    {
    }

    public Node constructBinaryTree(List preOrder, List inOrder)
    {
        Node node = null;
        List leftPreOrder;
        List rightPreOrder;
        List leftInorder;
        List rightInorder;
        int inorderPos;
        int preorderPos;

        if ((preOrder.size() != 0) && (inOrder.size() != 0))
        {
            //  Assign the first element of preorder traversal as root
            node = new Node();
            node.data = ((Integer) preOrder.get(0)).intValue();

            //  Based upon the current node data seperate the traversals into leftPreorder, rightPreorder,
            //  leftInorder, rightInorder lists
            inorderPos = inOrder.indexOf(preOrder.get(0));
            leftInorder = inOrder.subList(0, inorderPos);
            rightInorder = inOrder.subList(inorderPos + 1, inOrder.size());

            preorderPos = leftInorder.size();
            leftPreOrder = preOrder.subList(1, preorderPos + 1);
            rightPreOrder = preOrder.subList(preorderPos + 1, preOrder.size());

            node.left = constructBinaryTree(leftPreOrder, leftInorder);
            node.right = constructBinaryTree(rightPreOrder, rightInorder);
        }

        return node;
    }

    public static void main(String[] args)
    {
        ArrayList preOrder = new ArrayList();
        preOrder.add(new Integer(1));
        preOrder.add(new Integer(2));
        preOrder.add(new Integer(4));
        preOrder.add(new Integer(8));
        preOrder.add(new Integer(9));
        preOrder.add(new Integer(10));
        preOrder.add(new Integer(11));
        preOrder.add(new Integer(5));
        preOrder.add(new Integer(3));
        preOrder.add(new Integer(6));
        preOrder.add(new Integer(7));

        ArrayList inOrder = new ArrayList();
        inOrder.add(new Integer(8));
        inOrder.add(new Integer(4));
        inOrder.add(new Integer(10));
        inOrder.add(new Integer(9));
        inOrder.add(new Integer(11));
        inOrder.add(new Integer(2));
        inOrder.add(new Integer(5));
        inOrder.add(new Integer(1));
        inOrder.add(new Integer(6));
        inOrder.add(new Integer(3));
        inOrder.add(new Integer(7));

        /*
        Constructs following tree
                        1
                    2         3
                4       5  6     7
            8       9
                 10     11
                                                        */
        InorderPreorder inPreTree = new InorderPreorder();
        Node node = inPreTree.constructBinaryTree(preOrder, inOrder);

        //  For Testing
        BinaryTree binaryTree = new BinaryTree();
        System.out.println("\n Inorder Traversal of constructed tree is ");
        binaryTree.printInorder(node);
        System.out.println("\n Preorder Traversal of constructed tree is ");
        binaryTree.printPreorder(node);
        System.out.println("\n Levelorder Traversal of constructed tree is ");
        binaryTree.printLevelOrder(node);
    }
}

Passing index of preorder and inorder traversals and using the same input list to construct tree

The first method is not space efficient because we are constructing new lists for left and right subtree for each and every iteration. The following program just passes index of inorder and preorder traversals and uses the same input list to construct binary tree.

package ds;

import java.util.ArrayList;
import java.util.List;

public class InorderPreorderEfficient
{
    public InorderPreorderEfficient()
    {
    }

    public Node constructBinaryTree(List preOrder, List inOrder,
        int preOrderIndex, int inOrderIndex, int length)
    {
        if (length == 0)
        {
            return null;
        }

        Node node = new Node();
        int nodeData = ((Integer) preOrder.get(preOrderIndex)).intValue();
        node.data = nodeData;

        //  Need to calculate relative index where the current noda data is present in inOrder traversal
        int rootIndex = 0;

        for (int count = inOrderIndex; count < inOrder.size(); count++)
        {
            int inOrderData = ((Integer) inOrder.get(count)).intValue();

            if (inOrderData == nodeData)
            {
                break;
            }

            rootIndex++;
        }

        node.left = constructBinaryTree(preOrder, inOrder, preOrderIndex + 1,
                inOrderIndex, rootIndex);

        node.right = constructBinaryTree(preOrder, inOrder,
                preOrderIndex + rootIndex + 1, inOrderIndex + rootIndex + 1,
                length - (rootIndex + 1));

        return node;
    }

    public static void main(String[] args)
    {
        ArrayList preOrder = new ArrayList();
        preOrder.add(new Integer(1));
        preOrder.add(new Integer(2));
        preOrder.add(new Integer(4));
        preOrder.add(new Integer(8));
        preOrder.add(new Integer(9));
        preOrder.add(new Integer(10));
        preOrder.add(new Integer(11));
        preOrder.add(new Integer(5));
        preOrder.add(new Integer(3));
        preOrder.add(new Integer(6));
        preOrder.add(new Integer(7));

        ArrayList inOrder = new ArrayList();
        inOrder.add(new Integer(8));
        inOrder.add(new Integer(4));
        inOrder.add(new Integer(10));
        inOrder.add(new Integer(9));
        inOrder.add(new Integer(11));
        inOrder.add(new Integer(2));
        inOrder.add(new Integer(5));
        inOrder.add(new Integer(1));
        inOrder.add(new Integer(6));
        inOrder.add(new Integer(3));
        inOrder.add(new Integer(7));

        /*
        Constructs following tree
                        1
                    2         3
                4       5  6     7
            8       9
                 10     11
                                                        */
        InorderPreorderEfficient inPreTree = new InorderPreorderEfficient();
        Node node = inPreTree.constructBinaryTree(preOrder, inOrder, 0, 0, 11);

        //  For Testing
        BinaryTree binaryTree = new BinaryTree();
        System.out.println("\n Inorder Traversal of constructed tree is ");
        binaryTree.printInorder(node);
        System.out.println("\n Preorder Traversal of constructed tree is ");
        binaryTree.printPreorder(node);
        System.out.println("\n Levelorder Traversal of constructed tree is ");
        binaryTree.printLevelOrder(node);
    }
}

Similarly based on other pair of traversals, binary tree can be constructed.

References:

http://en.wikipedia.org/wiki/Tree_traversal

Please write comments if you find any of the above algorithms or codes incorrect, or find better ways to solve the same problem.

About these ads

9 Responses to Rebuild a binary tree from Inorder and Preorder traversals

  1. rangaraju says:

    I appreciate your efforts in bringing up new Qs with Answers. keep up the good work.

  2. [...] Read the original article. Tags: Binary Tree Comments RSS feed [...]

  3. RandomSurfer says:

    great work! it really helps to understand concepts and increases confidence to tackle an interview .. keep it coming :)

  4. Addon Scripte…

    [...]Rebuild a binary tree from Inorder and Preorder traversals « Programming Interview Questions[...]…

  5. nisha says:

    thanx 4 the procedure to rebouild a tree…its really helpful 4 novice..

  6. mohit. says:

    thanks 4 the procedure to rebuild a tree…its really helpful.

  7. nima says:

    Quick question, shouldn’t there be some error checking for this. Such as if we have an inorder of {1,2,3} and preOrder={2,1,3} once the left side of the tree has a length of zero (meaning that the root is 0), wont it go to the right side of tree that has a preOrderIndex length which is greater than the size of the array. So

    shouldnt we have another base case?

    if(preOrderIndex > pLength) {

    return null

    }

    Because it will not be able to find the NodeData since the preOrderIndex has a length greater than the size of the array.

    Am I making sense? Or am I wrong?

  8. vishnujayvel says:

    Reblogged this on coding hangover.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 57 other followers

%d bloggers like this: