A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

2 added 49 characters in body

We know post-order,

post L(x)     => [x]
post N(x,l,r) => (post l) ++ (post r) ++ [x]


and pre-order

pre L(x)     => [x]
pre N(x,l,r) => [x] ++ (pre l) ++ (pre r)


and in-order traversal resp. sequentialisation.

in L(x)     => [x]
in N(x,l,r) => (in l) ++ [x] ++ (in r)


One can easily see that neither describes a given tree uniquely, even if we assume pairwise distinct keys/labels.

Which combinations of the three can be used to that end and which can not?

Positive answers should include an (efficient) algorithm to reconstruct the tree and a proof (idea) why it is correct. Negative answers should provide counter examples, i.e. different trees that have the same representation.

We know post-order,

post L(x)     => [x]
post N(x,l,r) => (post l) ++ (post r) ++ [x]


and pre-order

pre L(x)     => [x]
pre N(x,l,r) => [x] ++ (pre l) ++ (pre r)


and in-order traversal resp. sequentialisation.

in L(x)     => [x]
in N(x,l,r) => (in l) ++ [x] ++ (in r)


One can easily see that neither describes a given tree uniquely.

Which combinations of the three can be used to that end and which can not?

Positive answers should include an (efficient) algorithm to reconstruct the tree and a proof (idea) why it is correct. Negative answers should provide counter examples, i.e. different trees that have the same representation.

We know post-order,

post L(x)     => [x]
post N(x,l,r) => (post l) ++ (post r) ++ [x]


and pre-order

pre L(x)     => [x]
pre N(x,l,r) => [x] ++ (pre l) ++ (pre r)


and in-order traversal resp. sequentialisation.

in L(x)     => [x]
in N(x,l,r) => (in l) ++ [x] ++ (in r)


One can easily see that neither describes a given tree uniquely, even if we assume pairwise distinct keys/labels.

Which combinations of the three can be used to that end and which can not?

Positive answers should include an (efficient) algorithm to reconstruct the tree and a proof (idea) why it is correct. Negative answers should provide counter examples, i.e. different trees that have the same representation.

1

# Which combinations of pre-, post- and in-order sequentialisation are unique?

We know post-order,

post L(x)     => [x]
post N(x,l,r) => (post l) ++ (post r) ++ [x]


and pre-order

pre L(x)     => [x]
pre N(x,l,r) => [x] ++ (pre l) ++ (pre r)


and in-order traversal resp. sequentialisation.

in L(x)     => [x]
in N(x,l,r) => (in l) ++ [x] ++ (in r)


One can easily see that neither describes a given tree uniquely.

Which combinations of the three can be used to that end and which can not?

Positive answers should include an (efficient) algorithm to reconstruct the tree and a proof (idea) why it is correct. Negative answers should provide counter examples, i.e. different trees that have the same representation.