Problem is
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.
I constructed the tree :
This is ternary tree .
What I'm asking:
- Is it correct tree ?
- Is/Are another solution(s) possible ?
The tree is correct and unique. The descendants of node $k$ are precisely the nodes $j\gt k$ for which $j$ appears before $k$ in post-order; that uniquely determines the tree you've drawn.