1.7k views
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
edited | 1.7k views
0
i think this problem is np-omplete problem and a non deterministic machine can draw the tree.??
0
How to draw it?
+2
0
@ Arjun sir plz provide any method for this ques

Answer: The tree is a ternary tree.

by Boss (33.8k points)
selected by
+3
can you give algorithm ? How you came up with this ?
0
I still don't get how did we get this tree ? What's the algorithm or technique for it ? @Arjun sir ?
+6
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.
0
@ Arjun sir is there is any way to solve this  problem ? or question is ambigous ?
0
how to construct this tree?
+3
why not this to be a binary tree?
0
How did you arrive at the solution?
+2
0
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?
0
0
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..?
0

@Shubham Aggarwal

+1
@shaikh Masthan bro you are awesome.

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 ?

10,11,12

what is the post order of those elements?

10,11,12

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

NO

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.

by Veteran (61.9k points)
0
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
0
thank u very much approx 5-6 times need to do very tricky question
0

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

0
thanks for the solution sir it should be the best ans.
0
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
0
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
0

https://www.geeksforgeeks.org/if-you-are-given-two-traversal-sequences-can-you-construct-the-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."

0
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 ?
0

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.

0
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.
0
thanks sir.
0

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

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

By brute force tried binary,ternary !
0
Great message

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

@Arjun  sir

check..

by (79 points)
0

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

1
2