The GATE Grind

GATE 2024 CS (CS2) – Question 39

Programming and Data Structures · Trees and Binary Search Trees · 2 marks · Multiple choice

You are given a set $V$ of distinct integers. A binary search tree $T$ is created by inserting all elements of $V$ one by one, starting with an empty tree. The tree $T$ follows the convention that, at each node, all values stored in the left subtree of the node are smaller than the value stored at the node. You are not aware of the sequence in which these values were inserted into $T$, and you do not have access to $T$. Which one of the following statements is TRUE?

  1. Inorder traversal of $T$ can be determined from $V$
  2. Root node of $T$ can be determined from $V$
  3. Preorder traversal of $T$ can be determined from $V$
  4. Postorder traversal of $T$ can be determined from $V$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) Inorder traversal of $T$ can be determined from $V$

Explanation

Inorder traversal of a BST is always the sorted order of its keys, independent of insertion order. Root, preorder and postorder depend on insertion sequence.