GateAI
Binary Search Trees

GATE CSE 2024 Set 2 · Q39

MCQ2 marksEasy

Time

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

Which one of the following statements is TRUE?

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: A) Inorder traversal of T can be determined from V

Binary Search Trees

By definition of a Binary Search Tree (BST), for every node uu, all keys in its left subtree are strictly smaller than the key at uu, and all keys in its right subtree are strictly greater than the key at uu.

An inorder traversal (Left →\to Root →\to Right) visits the nodes in strictly non-decreasing (ascending) order. Since the set VV contains distinct integers, the inorder traversal of any BST constructed from VV is always the unique sequence of elements of VV sorted in ascending order, regardless of the order in which the elements were inserted.

In contrast:

  • The root node is the very first inserted element, which depends on the insertion sequence.

  • The preorder and postorder traversals depend directly on the structural shape of TT, which also depends on the insertion sequence.

Therefore, only the inorder traversal of TT can be uniquely determined from the set VV alone.

Hence, (A) is the correct statement.

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Binary Search Trees previous year question is Q39 of the GATE CSE 2024 Set 2 paper. Find more GATE CSE PYQs on Binary Search Trees in Programming and Data Structures, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Binary Search Trees PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Binary Search Trees in GATE CSE

Binary Search Trees has 21 GATE CSE PYQs across 17 papers from 2011 to 2026. 6 of them are 2-mark MCQs like this one, and it is the only one in GATE CSE 2024 Set 2.

How GATE tests Binary Search Trees

More from GATE CSE 2024 Set 2

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2024 Set 2 · Q39 · MCQ

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?

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.