The Gateway to Computer Science Excellence
+24 votes
A rooted tree with $12$ nodes has its nodes numbered $1$ to $12$ in pre-order. When the tree is traversed in post-order, the nodes are visited in the order $3, 5, 4, 2, 7, 8, 6, 10, 11, 12, 9, 1$.

Reconstruct the original tree from this information, that is, find the parent of each node, and show the tree diagrammatically.
in DS by
edited by | 2.4k views
i think this problem is np-omplete problem and a non deterministic machine can draw the tree.??
How to draw it?
@ Arjun sir plz provide any method for this ques

Gatebook has hidden above link answer. We have archived link available anyway.

3 Answers

+13 votes
Best answer

Answer: The tree is a ternary tree.

selected by
can you give algorithm ? How you came up with this ?
I still don't get how did we get this tree ? What's the algorithm or technique for it ? @Arjun sir ?
Ambiguity is caused when we use pre-order and post-order to derive the original tree .. so basically we cannot come up with an exact answer.
@ Arjun sir is there is any way to solve this  problem ? or question is ambigous ?
how to construct this tree?
why not this to be a binary tree?
How did you arrive at the solution?
What about the statement "It is not possible to construct a binary tree uniquely whose pre-order and post-order traversals are given" this is true for only binary trees?
i am not able to understand it please help.
Still not able to understan this question please explain briefly . as it is choosen best answer so at least show step how to construct such tree in which preorder and postorder is given..?

@Shubham Aggarwal

check my answer.

@shaikh Masthan bro you are awesome.
+21 votes

question is:-

PRE ORDER :- 1,2,3,4,5,6,7,8,9,10,11,12

POST ORDER :- 3,5,4,2,7,8,6,10,11,12,9,1.

Draw the tree, but in the question they didn't specify it is binary or ternary or something else.

i hope they forget it by mistake.

Just assume is it can be a Binary tree?

Pre oder :- Data, Left, Right ( 1st node should be root )

( first node should be root, next to the root node is should be left node of root, if in post-order it is not in place of 2nd last node )

Post order :-  Left, Right, Data

( last node should be root, before the last node it should be right node of root, if in pre-order it is not in place of 2nd node )


Now i conclude that, 9 is right of 1 and 2 is left of 1

PRE ORDER :- 1,${\color{Red} {2,3,4,5,6,7,8}} ,{\color{Green}{9,10,11,12}}$

POST ORDER :- ${\color{Red} {3,5,4,2,7,8,6}},{\color{Green} {10,11,12,9}}$,1.

clearly observe that, the right of root contains 9,10,11,12 ===> leave 9 due to it is fixed at immediate right of root.

so remaining elements are 10,11,12.

what is pre-order of those elements ?


what is the post order of those elements?


Is it possible in Binary Tree? (check all 5 trees which can formed by 3 nodes)


Just assume it can be a Ternary Tree

PRE ORDER :- 1,2,3,4,5,6,7,8,9,10,11,12

POST ORDER :- 3,5,4,2,7,8,6,10,11,12,9,1.

2 is left most and 9 is right most, the childs of 9 is 10,11,12 from left to right.

For clear image

if you really particular about (Left,Middle,Right) nodes

then more than one tree can possible. But how many?

for 6, there are 2 childrens,but there are three links ===> 3 possibilities as (7,8,_) , (7,_,8),(_,7,8)

for 4, there is 1 child only,but there are three links ===> 3 possibilities as (5,_,_) , (_,5,_),(_,_,5)

for 2, there are 2 childrens,but there are three links ===> 3 possibilities as (3,4,_) , (3,_,4),(_,3,4)

==> By Multiplication Theorem, total trees which lead to given Pre-order and Post-order = 3*3*3 = 9
thank u very much approx 5-6 times need to do very tricky question

Very elaborate answer, understood after all. Thanks @Shaik Masthan

thanks for the solution sir it should be the best ans.
can we say that as with a given pre and post we can't derive a unique binary tree so it will be for sure not a binary tree
No... sometimes we can draw a unique binary tree with the help of pre and post orders, but not always !

in this question those two orders are conflicting due to that we can't form a binary tree

but they say "It depends on what traversals are given. If one of the traversal methods is Inorder then the tree can be constructed, otherwise not."

just check :

Pre-order = 1,2,7,8,5,6,9

Post-order = 7,8,2,6,9,5,1

can't you construct Unique Binary tree ?

Q. State whether the following statements are TRUE or FALSE:

It is possible to construct a binary tree uniquely whose pre-order and post-order traversals are given?

than ans should be TRUE as it is possible to construct a binary tree uniquely.



read my comment... i am not saying it is always !

i am saying sometimes we can construct.

If you are not getting, how this answer is correct ? i mean even with ternary tree i didn't assume it is searching tree like binary search tree.
thanks sir.

@Shaik Masthan...bro how you decided it is 3 aray tree..i.e ternary tree...I didn't get it

It should have to provide in question but unfortunately it doesn't !

By brute force tried binary,ternary !
Great message
0 votes

why this cant be an answer...(i am assuming this is a BST..cause no restrictions are given.. assumption can be anything) ???

@Arjun  sir

@Rajarshi Sarkar check..



preorder should be 1,2,3,4,5,6,7,8,9,10,11,12

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,315 questions
60,433 answers
95,257 users