in DS recategorized by
5,431 views
32 votes
32 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 recategorized by
5.4k views

4 Comments

i think this problem is np-omplete problem and a non deterministic machine can draw the tree.??
0
0
How to draw it?
0
0
@ Arjun sir plz provide any method for this ques
0
0

3 Answers

39 votes
39 votes
Best answer
  • 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$

We can draw the tree, but in the question it is not specified if it is binary or ternary or something else.

Lets assume it is a binary tree.

Pre oder: Data, Left, Right (First node should be root)

(First node should be root, next to the root node should be left node of root, if in the post-order it is not in the second last position)

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 the second position)

Now we can 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.

We can clearly observe that, the right of root contains $9,10,11,12 \implies$ we can leave $9$ as its position is fixed as 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


Now lets consider a Ternary Tree

  • PRE ORDER $:\overbrace{\boxed{1}}^{\text{root}},\overbrace{2,3,4,5,6,7,8,9,10,11,12}^{\text{non-root elements}}$
  • POST ORDER $:\underbrace{3,5,4,2,7,8,6,10,11,12,9}_{\text{non-root elements}},\boxed{1}$

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

  • PRE ORDER : $2,3,4,5,6,7,8,9,\overbrace{\boxed{10,11,12}}^{\text{subtree of 9, but order unknown}}$
  • POST ORDER : $3,5,4,2,7,8,6,10,11,12,\overbrace{\boxed{9}}^{\text{Right most child of root}}$

Check all the elements in the preorder after $9-$ those should be children of $9.$

After checking the preorder and postorder we can conclude that all those elements are at the same level in the order $10-11-12.$

  • PRE ORDER : $\overbrace{\boxed{2}}^{\text{Should be the leftmost child of root}\\\text{Elements before 2 in the postorder}\\\text{must be children of 2} },3,4,5,6,7,8$
  • POST ORDER : $\underbrace{\boxed{3,5,4}}_{\text{Should be a subtree of $2$}\\\text{but order in unknown}},2,7,8,6$

How we separated $3,4$ and $5$ as two parts?

Check the preorder: $3\implies$ elements before $3$ in the postorder are in the same subtree as $3$ but there are no elements before $3.$

Therefore $3$ is separated from $4$ and $5.$

How we fixed $4$ and $5$ in that order?

Check the preorder: $4\implies$ elements before $4$ in the postorder are in the same subtree of $4.$ Therefore $5$ is in the same subtree of $4.$

  • PRE ORDER : $6,7,8$
  • POST ORDER : $\underbrace{\boxed{7,8}}_{\text{Should be a sub-tree of 6}\\\text{but order is unknown}},6$

We can easily understand that $6$ is the child of root. Elements before $6$ in the postorder forms subtree of $6.$

How we fixed $7$ and $8$ in that order?

Check the preorder: $7\implies$ elements before $7$ in the postorder are in the same subtree of $7$ but there are no elements before $7.$

Therefore $7$ and $8$ are separated.

edited by

4 Comments

arey mere bhai… if it was possible to construct a unique binary tree from just the post order and pre order than why the hell have we been studying all this time that “we cannot construct a unique binary tree given only preorder and postorder. We should at least have either pre + inorder or post + inorder if we want to construct the tree uniquely otherwise there will be 2nCn/n+1 possible solutions.

0
0

we cannot construct a unique binary tree given only preorder and postorder

That doesn't mean all the time, you can't create unique BST. Sometimes you can create !

read previous comments on this answer 

0
0
Best Explanation by any Teacher.Pure conceptual stuff🌟
0
0
14 votes
14 votes

Answer: The tree is a ternary tree.

4 Comments

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
0

@Shubham Aggarwal

check my answer.

0
0
@shaikh Masthan bro you are awesome.
2
2
1 vote
1 vote

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

1 comment

@blackcloud 

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

0
0

Related questions