GATE CS 2024 Set 2 Q.39: Binary Trees, Binary Search Trees and Balanced Trees

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?

Inorder traversal of $T$ can be determined from $V$

Root node of $T$ can be determined from $V$

Preorder traversal of $T$ can be determined from $V$

Postorder traversal of $T$ can be determined from $V$

Official answer and solution

Official answer: A
From: Official GATE 2024 answer key

Solution

Use the fundamental property that the inorder traversal of any BST on a set $V$ of keys is always the keys of $V$ in sorted ascending order.

Regardless of the insertion sequence or the resulting shape of the Binary Search Tree $T$ , an inorder traversal (Left -> Node -> Right) of a BST always visits the keys in strictly increasing sorted order. Since the set $V$ of keys is known, sorting $V$ uniquely determines the inorder traversal of $T$ . By contrast, the root node, preorder traversal, and postorder traversal all depend on the order in which elements of $V$ were inserted.

Final answer

Option (A)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2024 Computer Science and Information Technology - Set 2 (CS2)
Question: 39 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source