The GATE Grind

GATE 2024 DA – Question 28

Programming, Data Structures and Algorithms · Stacks, queues, linked lists, trees and hash tables · 1 mark · Multiple select

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?

  1. (i) and (ii)
  2. (ii) and (iii)
  3. (i) and (iii)
  4. (ii) only

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) (i) and (ii); (B) (ii) and (iii); (C) (i) and (iii)

Explanation

For a binary tree in general, preorder with inorder, or postorder with inorder, give a unique tree. For a full binary tree (every node has 0 or 2 children), preorder with postorder also gives a unique tree, because the second element of the preorder is the root of the left subtree, and its position in the postorder shows how large that subtree is. The inorder traversal alone is not enough.