2
$\begingroup$

Supposing a tree T has the identical:

  1. Pre-order traversal and in-order traversal
  2. Pre-order traversal and post-order traversal
  3. In-order traversal and post-order traversal

How does T look like?

From the previous discussion in SO, I learned that pre- and post-order are same iff. only one node is in the T.

How about the left two conditions?

I suppose that only purely left-skewed tree can make post- and in-order the same, and only right-skewed tree can make pre- and in-order the same.

Am I on the right way?


Edit: To avoid being solely a 'yes' or 'no' problem, the actual doubt is that how to prove this statement, but I have a idea about the proofs using contradiction. So maybe this problem is a little redundant.

$\endgroup$
  • 1
    $\begingroup$ Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. If you just want general feedback, you are welcome to visit us in Computer Science Chat. $\endgroup$ – FrankW Oct 21 '14 at 5:15
3
$\begingroup$

A proper proof uses the recursive definitions of the tree-orders. Here is a sketch.

For inorder the recursive definition is: in(left) - root - in(right). For postorder we similarly have: post(left) - post(right) - root.

Look at the position of root in both orders. If we want this to be the same we need to have there are no nodes in in(right) which means the right subtree (at the root) is empty. Same for the root at other levels.

$\endgroup$
2
$\begingroup$

Hendrik is almost right but did not conclude well. Therefore, I am giving a more comprehensive answer.

In the followings, r denotes root, l denotes left sub-tree, and r denotes right sub-tree. Now, let's consider each case separately, starting from the second one.

  • Pre-order is the same as post-order: In this case r-pre(l)-pre(r) should be the same as post(l)-post(r)-r. For them to be equal both r and l should be empty trees (null). So the tree should only have one node as follows:

                             a
                            / \
                         null null
    
  • Pre-order is the same as In-order: In this case r-pre(l)-pre(r) should be the same as in(l)-r-in(r). For them to be equal we need to get rid of in(l) enforcing the left sub-tree to be empty (null). However, in(r) should be the same as pre(r). Now again we need in-order traversal to be the same as pre-order traversal. Although formally an induction proof is required for this case, intuitively one can observe that the tree should only have right child at every node (not necessarily a one node tree). Here is an example:

                             a
                            / \
                         null  b
                              / \
                           null  c
                                / \
                                 ...
    
  • In-order is the same as post-order: This is the same as the previous case but the tree should only have left child at every node.

                             a
                            / \
                           b  null
                          / \
                         c  null
                        / \
                       ...
    
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.