Thread: Theoritical question in trees structures

Hello dear members, i have a theoritical question in trees structures

We have three ways to travel in a tree (pre order, in order and post order)
Could you tell me when we cant be sure how to draw the tree
when we have the results of two of three ways to travel the tree.

Thanks in advance!

I can only assume you are not given the traversal types for each sequence, otherwise it would be trivial to recreate the tree. I certainly can't answer this in any formal or mathematical way, but I will give you some things to maybe steer you in the right direction. Note, these are my personal observations and I believe them to be correct, but have no proof. Somebody with a stronger data structure and algorithm background may come prove me wrong.

1. The in-order traversal provides no clue as to structure, it simply lists the nodes out in sorted order.
2. Given two out of the three traversal types, you are only guaranteed that one of them is pre- or post-order traversal
3. You can't tell just by looking at it whether a sequence is pre- or post-order.
4. It is possible to create a binary tree whose pre- or post-order traversals visit nodes in the same order as an in-order traversal.
5. For such a tree, if the pre-order matches the in-order, the post-order will visit nodes in the reverse order and vice-versa.

You can use items 1, 2 and 3 to make a general statement about when you can/can not determine structure of any tree. Trees that fit items 4 and 5 have a specific structure for which it is always impossible to determine structure from two unspecified traversals, even if given all three traversals unspecified.

Hope those hints get you thinking along the right lines without giving the answer away.

I really thank you for your asnwer. I found the 'solution'

....i have the same pre-order and post-order
for two different trees

I hope I'm not misunderstanding your comment, but you can't have the same pre-order and post-order for any tree, except a tree with exactly one node (which is trivial to recreate). If you mean same pre- and in-order for one shape of tree, and the same post- and in-order for a second shape of tree, that's good, but that only covers items 4 and 5, for which even all 3 traversals wont help you.

Did you figure out what conclusion items 1, 2 and 3 lead you to? The shape of the tree is irrelevant there. Given two traversals, can you figure out what the tree is?
What if I give you 1, 3, 4, 7, 9, 10 and 7, 3, 1, 4, 9, 10?
What if I give you 1, 3, 4, 7, 9, 10 and 1, 4, 3, 10, 9, 7?
Now what if I give you 7, 3, 1, 4, 9, 10 and 1, 4, 3, 10, 9, 7?

Do you see what you need to accurately recreate any tree in general? Do you see how the conclusion you draw from 4 and 5 make it impossible to recreate the tree in those specific cases?

Hint: It's clear in the first two that one is a in-order, but are the others pre- or post-order traversals? Is it possible to tell?

Code:

(A)                     (A)
    /                           \
 (B)                            (B)
  /                                 \
(C)                                 (C)

both tress have the same pre order: 1,2,3
and post order: 3,2,1. So we cant tell from which tree the 'came'

Another assumption that I should have stated is that these are binary search trees, i.e. that their nodes are stored in order. The right children must be greater than the root which is greater than the left children. The trees you showed do both have the the same pre- and post-order, but it's not really valid because you aren't using the right node ordering. Your two trees were the right shape, but should look like this:

Code:

    A                  C
   /                    \
  B                      B
 /                        \
C                          A
in: A, B, C         in: A, B, C
pre: A, B, C        pre: C, B, A
post: C, B, A       post: A, B, C

I wasn't focusing on two trees with the same pre- and post-ordering, but rather a tree for which either the pre- or post-order traversal was identical to the in-order traversal, as we have in the above example. In this case, even if you were given all 3 traversals, without knowing which was which, you couldn't reliably reconstruct the tree. Those two trees above have exactly the same 3 traversal paths, just with the pre- and post-orders switched.

Did you figure out the general case yet? It has to do with which two traversals you have.

This was actually a great problem, I've really been enjoying it.