Construct tree from InOrder and
PreOrder traversals
PreOrder
is DLR and InOrder is LDR
That
means, first element of PreOrder is the root of the tree.
However,
in InOrder, root is found after all its left subtree has been
traversed.
This
implies that left part from start to root in InOrder is the left
subtree.
From
PreOrder, take same number of characters after root.
These
two smaller subsequences from pre-order and in-order can be used to
form a left subtree and similarly the right subtree.
Example:
Inorder
sequence: D B E A F C
Preorder
sequence: A B D E C F
So,
root is A
InOrder
left subtree has 3 characters - DBE
Take
similar number of characters from InOrder - BDE
Form
subtree for these two and make it left child.
Remaining
part is FC from InOrder and CF from PreOrder.
Follow
the recursion to form right subtree.

|