1
$\begingroup$

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 . enter image description here

What I'm asking:

  1. Is it correct tree ?
  2. Is/Are another solution(s) possible ?
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ So, I concluded (1) we can construct many trees from given preorder and postorder., (2) construction of tree from preorder and postorder may not be unique . Which statement I should follow ? Is (2) statement right ? $\endgroup$
    – Display Name is missing
    Sep 14, 2015 at 13:23
  • $\begingroup$ @user4791206: Are you asking about the general case? (Since I've already answered that question for this particular case.) I would have thought that specifying the descendants of each node uniquely fixes a tree. Do you disagree? Do you have a counterargument or counterexample? $\endgroup$
    – joriki
    Sep 14, 2015 at 13:44
  • $\begingroup$ yes sir , I am asking for general case in above my comment . Thanks for help. $\endgroup$
    – Display Name is missing
    Sep 14, 2015 at 14:16
  • $\begingroup$ @user4791206: I'm not sure I've made myself clear. I believe that the tree is also unique in the general case, and I believe I've given an argument for that. If you disagree, you should provide a counterargument or a counterexample, or point out a flaw in my argument. $\endgroup$
    – joriki
    Sep 14, 2015 at 15:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .