Consider the following tree traversals on a full binary tree: (i) Preorder…
2024
Consider the following tree traversals on a full binary tree:
(i) Preorder
(ii) Inorder
(iii) Postorder
Which of the following traversal options is/are sufficient to uniquely reconstruct the full binary tree?
- A.
(i) and (ii)
- B.
(ii) and (iii)
- C.
(i) and (iii)
- D.
(ii) only
Attempted by 337 students.
Show answer & explanation
Correct answer: A, B, C
Answer: Preorder and Inorder, Inorder and Postorder, and Preorder and Postorder (given the tree is full) all suffice to uniquely reconstruct the tree.
Why each pair works:
Preorder + Inorder: The first value in Preorder is the root. Locate that value in Inorder to split the sequence into left and right subtree inorder lists. The lengths of those lists tell you how many nodes belong to each subtree in the preorder sequence; recurse.
Inorder + Postorder: The last value in Postorder is the root. Locate it in Inorder to split into left and right subtree inorder lists. The sizes determine how to split the Postorder sequence between left and right subtrees; recurse.
Preorder + Postorder (for a full binary tree): Preorder gives the root and then the root of the left subtree as the next element. Find that left-subtree root in Postorder to determine the extent (size) of the left subtree. Because the tree is full (each internal node has two children), there are no ambiguous cases with single-child nodes, so the sizes uniquely determine subtree boundaries and recursion reconstructs the tree.
Note: A single traversal (e.g., Inorder alone) is not sufficient because it does not indicate root positions or subtree boundaries. Also, Preorder+Postorder are insufficient for general binary trees but become sufficient when the tree is known to be full.