Supposing a tree T has the identical:
- Pre-order traversal and in-order traversal
- Pre-order traversal and post-order traversal
- 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.