IAE Academy

GATE 2024 CS2 Q.39: solution and answer

GATE 2024 · CS2Q.39 · 2 marks · MCQ

You are given a set of distinct integers. A binary search tree is created by inserting all elements of one by one, starting with an empty tree. The tree 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 , and you do not have access to .

Which one of the following statements is TRUE?

  1. (A)

    Inorder traversal of can be determined from

  2. (B)

    Root node of can be determined from

  3. (C)

    Preorder traversal of can be determined from

  4. (D)

    Postorder traversal of can be determined from

See the question in the paper
GATE 2024 CS2 question 39Tap to open full size

Answer and solution

ANSWER

Inorder traversal of can be determined from

Official answer: ASource: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

  1. BST invariant: in any binary search tree built from a set V by inserting elements one by one, at every node all values in the left subtree are smaller than the node's value and (implicitly) all values in the right subtree are larger — this holds regardless of insertion order, since it is what defines the BST shape at each step.

  2. Inorder traversal visits left subtree, then the node, then right subtree. By induction on subtree size: the inorder traversal of any BST is exactly its elements listed in increasing numeric order. This is a structural property of BSTs, not dependent on how the tree was built.

  3. Since V is a fixed set of distinct integers, sorting V (an operation performable knowing only the set V) gives precisely the inorder sequence of T, for whichever insertion order produced T. So inorder traversal is fully determined by V alone — option (A) is TRUE.

  4. Root node (B): the root is whichever element of V was inserted first. Different insertion sequences of the same V give different roots — e.g. V = {1,2,3}: inserting order (2,1,3) makes 2 the root, while inserting order (1,2,3) makes 1 the root (with 2 and 3 as right descendants). So the root cannot be pinned down from V alone — (B) is false.

  5. Preorder traversal (C): preorder always begins with the root. Since the root varies with insertion order (shown above), the preorder sequence is not fixed by V alone — (C) is false.

  6. Postorder traversal (D): postorder always ends with the root, and its full sequence likewise depends on tree shape, which varies with insertion order — the same V = {1,2,3} example gives different postorder sequences for different insertion orders — (D) is false.

  7. Only the inorder traversal is invariant across every possible BST shape that V can produce, so the unique TRUE statement is (A).

KEY IDEA

A BST's inorder traversal is always its elements in sorted order — this is a consequence of the left-smaller/right-larger invariant at every node, true for every possible tree shape a set can produce, so it depends only on the set V, never on the insertion sequence that built T. Root, preorder, and postorder all depend on which element was inserted first, which V alone does not reveal.

WATCH OUT FOR

Assuming that because you "don't have access to T" nothing about it can be recovered from V, and picking "none of the traversals is determined" reasoning, or conversely assuming the root (the most naturally guessed structural feature) is fixed by the set — both miss that inorder order is a value-based, shape-independent property while root/preorder/postorder are insertion-order-dependent.

From the GATE 2024 CS2 paper. Every question of this paper · Download the full paper · All 26 Trees & heaps questions, with notes

More Trees & heaps questions