Consider the label sequences obtained by the following pairs of traversals on…
2004
Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely ?
(i) preorder and postorder
(ii) inorder and postorder
(iii) preorder and inorder
(iv) level order and postorder
- A.
(i) only
- B.
(ii), (iii)
- C.
(iii) only
- D.
(iv) only
Attempted by 447 students.
Show answer & explanation
Correct answer: B
Answer: The pairs that uniquely identify a labeled binary tree are inorder with postorder, and preorder with inorder.
Why inorder combined with preorder or postorder works:
Using preorder + inorder:
• The first element of the preorder sequence is the root. Locate that root in the inorder sequence to split the inorder into left-subtree and right-subtree sequences. The sizes of those parts tell you how to split the remainder of the preorder sequence into left and right subtree preorder sequences. Recurse on each subtree.
Using postorder + inorder:
• The last element of the postorder sequence is the root. Locate that root in the inorder sequence and split into left and right parts. The sizes determine how to split the rest of the postorder sequence into left and right subtree postorder sequences. Recurse on each subtree.
Because the inorder sequence gives the exact boundary between left and right subtrees, combining it with either preorder or postorder yields a unique reconstruction.
Why preorder + postorder can fail:
Preorder and postorder alone do not reveal subtree boundaries in the inorder sense. Simple counterexample: a root labeled A with a single left child labeled B, and a root A with a single right child B, both produce preorder sequence "A B" and postorder sequence "B A". These different trees share the same preorder and postorder, so the pair is not sufficient to uniquely identify the tree.
Why level-order + postorder can fail:
Level-order and postorder together also do not always determine the tree uniquely. Concrete example with labels A,B,C,D,E:
Tree 1 (structure): root A; left child B with left child D; right child C with right child E.
• Level-order: A B C D E
• Postorder: D B E C A
Tree 2 (different structure): root A; left child B with right child D; right child C with left child E.
• Level-order: A B C D E
• Postorder: D B E C A
These two distinct trees yield the same level-order and postorder sequences, so that pair does not guarantee uniqueness.
Final conclusion: inorder with postorder, and inorder with preorder, uniquely identify a labeled binary tree; preorder+postorder and level-order+postorder do not always.