ISRO-DEC2017-57

Question

The $in$-$order$ and $pre$-$order$ traversal of a binary tree are $\text{d b e a f c g}$ and $\text{a b d e c f g}$ respectively.The $post$-$order$ traversal of a binary tree is

1. $\text{e d b g f c a}$
2. $\text{e d b f g c a }$
3. $\text{d e b f g c a}$
4. $\text{d e f g b c a}$

Comments

option c

Answer 1

Traversal means processing each node a tree in some order.

1. Preorder: Visit node -->  Visit left tree -->   Visit right tree.
2. In-order: Visit left tree -->    Visit node    -->   Visit right tree.
3. 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

Answer 2

option C

d e b f g c a