Log In
1 vote

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

1 Answer

4 votes

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 answer
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$
asked Jun 9, 2016 in DS shivani2010 2.3k views
1 vote
2 answers
The efficient data structure to insert/delete a number in a stored set of number is Queue Linked list Doubly linked list Binary tree
asked Jul 20, 2016 in DS jothee 2.6k views
3 votes
1 answer
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$)
asked Jul 20, 2016 in DS jothee 2.2k views
24 votes
3 answers
Linked lists are not suitable data structures for which one of the following problems? Insertion sort Binary search Radix sort Polynomial manipulation
asked Oct 4, 2014 in DS Kathleen 8.3k views