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.

There would be an arrow and page design

Answercomposite key;