Question

Let PRE, IN, POST, LVL denote the preorder, postorder, inorder and level order traversal respectively. Then which of the following combinations of traversals is not sufficient to uniquely construct a binary tree?

• A. (PRE, IN)
• B. (POST, PRE)
• C. (POST, IN)
• D. (LVL, IN)

Answer 1

The correct option is B (POST, PRE)

PRE and POST are not sufficient, as we need one of them to determine the ROOT, and the other is supposed to determine the left subtree respectively, but in case of PRE and POST, both give the information only about the root. So the correct choice is (d).