[Math] Why is tree not uniquely possible with given preorder and postorder traversal

Question

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely?

1. preorder and postorder
2. inorder and postorder
3. preorder and inorder
4. level order and postorder

---

I've read that inorder is necessary to draw unique tree, well, I drawn the different tree with given options. I concluded that option $(2)$ and $(3)$ is true.

Can you explain formally please, why is tree not uniquely possible with given preorder and postorder traversal ?

Answer 1

Consider the trees shown below:

                    1                      1  
                   /                      /  
                  2                      2  
                 /                        \  
                3                          3

Both have preorder $123$, and both have postorder $321$, but they’re not the same binary tree. More generally, if a node has only one child, preorder and postorder do not contain enough information to determine whether that child is a left child or a right child.