Given the following preorder and inorder traversals, recover the original tree. preorder: c f d g h a b e inorder: g d h f c b e a

To build the original tree follow the steps described below:

In Preorder traversal the root always comes first in the list, so C is the root. In Inorder traversal the nodes those are left to C will be in left sub-tree of C and the nodes those are right to C will be in the right sub-tree of C.Now, in the left sub-tree (G D H F) , F comes first in the Preorder traversal, so F is the root. And as G D H are left to F in Inorder list so, they will be in left sub-tree of F. In the right sub-tree of C, (B E A),  A comes first in the Preorder list. So A is the root and B E will in left subtree of A.In left sub-tree of F, (G D H), D comes first in Preorder list, so D is the root and G is the left child of D and  H is the right child of D.Among (B E), B comes first in Preorder list, so B is the root and as E is right to B in Inorder, so is the right child of B

For more follow the diagram:

Explanation:

Preorder traversal visits the root of the tree first then the left sub-tree and then the right subtree.

Inorder traversal visits the left subtree first then the root and then the right subtree.

Islide through the whole