Register

GATE CSE 2015 | Set 1 | Question: 10

• edited by
11,998 views
35 35 votes

Which of the following is/are correct in order traversal sequence(s) of binary search tree(s)?

  1. $3, 5, 7, 8, 15, 19, 25$
  2. $5, 8, 9, 12, 10, 15, 25$
  3. $2, 7, 10, 8, 14, 16, 20$
  4. $4, 6, 7, 9, 18, 20, 25$
  1. I and IV only
  2. II and III only
  3. II and IV only
  4. II only

5 Answers

Best answer
41 41 votes

In order traversal of key are always in ascending order.

So, here I & IV th sequence  are in ascending order so Option A is Answer.

• edited by
0 0 votes

Answer

The correct option is (A) I and IV only.

Explanation

In a Binary Search Tree (BST), the Inorder Traversal always results in the keys being visited in strictly ascending (increasing) order. This is a fundamental property because the inorder traversal visits nodes in the sequence: Left Subtree $\to$ Root $\to$ Right Subtree.

To solve this question, we simply need to check which of the given sequences are sorted in ascending order:

  • I. 3, 5, 7, 8, 15, 19, 25: This sequence is in ascending order. (Valid)

  • II. 5, 8, 9, 12, 10, 15, 25: This sequence is not in ascending order ($12 > 10$). (Invalid)

  • III. 2, 7, 10, 8, 14, 16, 20: This sequence is not in ascending order ($10 > 8$). (Invalid)

  • IV. 4, 6, 7, 9, 18, 20, 25: This sequence is in ascending order. (Valid)

Since only sequences I and IV are correctly sorted, they are the only possible inorder traversals for a BST.

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 2015 | Set ...Next → · GATE CSE 2015 | Set ...
← Previous in category · GATE CSE 2015 | Set ...Next in category → · GATE CSE 2015 | Set ...
Position:
Show:

Related questions

60 60 votes
4 answers 4 answers
18.5k
18.5k views
Misbah Ghaya asked Feb 13, 2015
18,516 views
GATE CSE 2015 | Set 1 | Question: 23
What are the worst-case complexities of insertion and deletion of a key in a binary search tree?$\Theta(\log n)$ for both insertion and deletion$\Theta(n)$ for both inser...
36 36 votes
1 answers 1 answer
11.0k
11.0k views
Misbah Ghaya asked Feb 13, 2015
11,039 views
GATE CSE 2015 | Set 1 | Question: 32
Consider a max heap, represented by the array: $40, 30, 20, 10, 15, 16, 17, 8, 4$.$$\begin{array}{|l|l|}\hline \text{Array index} & \text{1} & \text{2} & \text{3} & \...
39 39 votes
4 answers 4 answers
18.2k
18.2k views
Misbah Ghaya asked Feb 13, 2015
18,245 views
GATE CSE 2015 | Set 1 | Question: 25
The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height $5$ are$63$ and $6$, respect...
34 34 votes
8 answers 8 answers
12.7k
12.7k views
go_editor asked Feb 14, 2015
12,725 views
GATE CSE 2015 | Set 3 | Question: 13
While inserting the elements $71, 65, 84, 69, 67, 83$ in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is$65$$67$$69$$83$