Question

Given the following Preorder and Inorder traversals, please recover the original tree. Preorder: C F D G H A B E Inorder: G D H F C B E A

Answer 1

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.