What if traversal order of two of pre-order, in-order and post-order is same?

Question

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.

Answer 1

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.

Answer 2

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
                      / \
                     ...