The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+18 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 Veteran (52.1k points)
edited by | 1.7k 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

3 Answers

+13 votes
Best answer

Answer: The tree is a ternary tree.

by Boss (33.8k points)
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.
+11 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

by Veteran (61.9k points)
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..

by (79 points)


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
49,807 questions
54,729 answers
79,909 users