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.

Reconstruct the original tree from this information, that is, find the parent of each node, and show the tree diagrammatically.

0

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

https://web.archive.org/web/20180116230508/http://thegatebook.in:80/qa/580/gate1994_8-trees

+13 votes

0

I think the following link will help:

http://math.stackexchange.com/questions/1434971/construction-of-rooted-tree-please-check-whether-my-solution-is-correct

http://math.stackexchange.com/questions/1434971/construction-of-rooted-tree-please-check-whether-my-solution-is-correct

0

I still don't get how did we get this tree ? What's the algorithm or technique for it ? @Arjun sir ?

+11

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

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?

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

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

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

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

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

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

0

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 ?

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

https://gateoverflow.in/80579/gate1987-2c

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.

+1

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.

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 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..

52,315 questions

60,433 answers

201,778 comments

95,257 users