[Solved]: What if traversal order of two of pre-order, in-order and post-order is same?

Problem Detail: 

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.

Asked By : Zhen Zhang

Answered By : Hendrik Jan

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 post(right) which means the right subtree (at the root) is empty. Same for the root at other levels.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32144