Traversal means processing each node a tree in some order.
- Preorder: Visit node --> Visit left tree --> Visit right tree.
- In-order: Visit left tree --> Visit node --> Visit right tree.
- Post order: Visit left tree --> Visit right tree --> Visit node.
Given that
in-order traversal: d b e a f c g
pre-order traversal: a b d e c f g
- As pre order started with a it is the root. Also, the nodes before a in inorder traversal is in left tree, nodes after a is right tree. a is root: { d b e} L | { f c g }R
- among {d b e} node b comes first in pre-order traversal. hence d and e are children of b. As in inorder traversal d comes before b, it is the left child and e is right child
- among {f c g} node c comes first in pre-order traversal. hence f and g are children of c. As in inorder traversal f comes before c, it is the left child and g is right child.
Result is
Post order traversal will be
d e b f g c a
Answer is 3