UGCNET-Sep2013-II: 21

1 vote
2.6k views

Consider the In-order and Post-order traversals of a tree as given below:

In-order: j e n k o p b f a c l g m d h i

Post-order: j n o p k e f b c l m g h I d a

The Pre-order traversal of the tree shall be

1. a b f e j k n o p c d g l m h i
2. a b c d e f j k n o p g l m h i
3. a b e j k n o p f c d g l m h i
4. j e n o p k f b c l m g h I d a
in DS
recategorized

If we consider given In-order and Post Order and construct the tree then no option is going to match .

This is the tree with given in-order  and post-order

If you traverse it from top to bottom left to right and print each element second time then we are going to get the exact in-order given in question .

if we print the element last time then we are going to get the post-order. But for pre-order it does not give us any option from given options, So correct pre-order should be

Preorder : abejknpofdglcmih

Related questions

1 vote
1
2.3k views
The min. number of nodes in a binary tree of depth d (root at level 0) is $(2^d + 1)$ $(2^{(d+1)} - 1)$ $d$ $d + 1$
1 vote
Suppose that the splits at every level of Quicksort are in proportion $1-\beta \text{ to } \beta$, where $0 < \beta \leq 0.5$ is a constant. The number of elements in an array is n. The maximum depth is approximately 0.5 $\beta$ Ig n 0.5 (1-$\beta$) Ig n -(Ig n)/(Ig $\beta$) -(Ig n)/Ig (1-$\beta$)