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