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.