The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
1.2k 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.
asked in DS by Veteran (59.6k points)
edited by | 1.2k 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

2 Answers

+13 votes
Best answer

Answer: The tree is a ternary tree.

answered by Boss (34.1k 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 ?
+4
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?
+1
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
i am not able to understand it please help.
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

check my answer.

0
@shaikh Masthan bro you are awesome.
+3 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 ?

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.

For clear image https://drive.google.com/open?id=1Q1NO4GFEIOhoDPGXeWactpFsk0OByCY7

answered by Boss (36.2k 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

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

42,599 questions
48,601 answers
155,673 comments
63,739 users