Dark Mode

5,431 views

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.

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

0

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.

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

14 votes

0

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