Answer:
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:
Step-by-step 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.