Binary Search Trees Questions and Answers

Q: Let P be the set of all integers from 1 to 15. Consider any order of insertion of the elements of P into a binary search tree that creates a complete binary tree.Which one of the following elements can NEVER be the third element that is inserted?

The element that can never be third is 5.The only complete binary search tree on 1 to 15 has root 8, then 4 and 12, then 2, 6, 10 and 14, and the odd numbers as leaves. In a BST every node must be inserted after all its ancestors, so the first element is 8 and the second is 4 or 12.The third element can therefore be the other child of the root, or a child of the second element: 4 (order 8, 12, 4), 2 (8, 4, 2) and 10 (8, 12, 10) are all possible.5 sits on the fourth level, below 8, 4 and 6, so at least three elements must come before it, and it can be inserted fourth at the earliest.

Q: 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?

The true statement is Inorder traversal of \(T\) can be determined from \(V\).An inorder traversal of a binary search tree visits the left subtree, the node, then the right subtree, so it always lists the keys in increasing order, whatever the tree's shape. Sorting V therefore gives the inorder traversal without knowing T.The root is the first value inserted, and the shape of the tree depends on the whole insertion order, so the root, the preorder and the postorder traversals all change with that order. For example, inserting 1, 2, 3 and 2, 1, 3 gives different roots and different preorders.

Q: Suppose that we have numbers between 1 and 500 in a binary search tree and want to search for the number 258. Which of the following sequences could not be the sequence of nodes examined ?

The impossible sequence is 3, 240, 398, 256, 399, 258.In a binary search each node examined narrows the range in which 258 must lie. Following this sequence:3 is less than 258, go right: the range is now above 3.240 is less than 258, go right: above 240.398 is greater than 258, go left: between 240 and 398.256 is less than 258, go right: between 256 and 398.399 lies outside that range, so it cannot be the next node examined.The other three sequences stay inside their shrinking ranges at every step; for example 453, 200, 448, 210, 363, 258 narrows to (200, 453), (200, 448), (210, 448), (210, 363), all containing 258.

Let P be the set of all integers from 1 to 15. Consider any order of insertion of the elements of P into a binary search tree that creates a complete binary tree.

Which one of the following elements can NEVER be the third element that is inserted?

A.4
B.2
C.10
D.5

Exam Year(s)

GATE CS - 2026,

Answer: D

The element that can never be third is 5.

The only complete binary search tree on 1 to 15 has root 8, then 4 and 12, then 2, 6, 10 and 14, and the odd numbers as leaves. In a BST every node must be inserted after all its ancestors, so the first element is 8 and the second is 4 or 12.

The third element can therefore be the other child of the root, or a child of the second element: 4 (order 8, 12, 4), 2 (8, 4, 2) and 10 (8, 12, 10) are all possible.

5 sits on the fourth level, below 8, 4 and 6, so at least three elements must come before it, and it can be inserted fourth at the earliest.

Discuss in Forum

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?

A.Inorder traversal of \(T\) can be determined from \(V\)
B.Root node of \(T\) can be determined from \(V\)
C.Preorder traversal of \(T\) can be determined from \(V\)
D.Postorder traversal of \(T\) can be determined from \(V\)

Exam Year(s)

GATE CS - 2024,

Answer: A

The true statement is Inorder traversal of \(T\) can be determined from \(V\).

An inorder traversal of a binary search tree visits the left subtree, the node, then the right subtree, so it always lists the keys in increasing order, whatever the tree's shape. Sorting V therefore gives the inorder traversal without knowing T.

The root is the first value inserted, and the shape of the tree depends on the whole insertion order, so the root, the preorder and the postorder traversals all change with that order. For example, inserting 1, 2, 3 and 2, 1, 3 gives different roots and different preorders.

Discuss in Forum

In-order traversal of a binary search tree gives the output in :

A.Non-increasing order
B.Unsorted
C.Non-decreasing order
D.Decreasing order

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

Answer: C

In-order traversal of a binary search tree gives the keys in Non-decreasing order.

In a binary search tree, every key in a node's left subtree is less than (or, if duplicates are allowed, not greater than) the node's key, and every key in its right subtree is greater. In-order traversal visits the left subtree, then the node, then the right subtree, so it lists the keys in ascending order.

'Non-decreasing' is the precise term when duplicate keys may occur. The traversal is never unsorted, and decreasing or non-increasing order would come from visiting the right subtree first, a reverse in-order traversal.

Discuss in Forum

Suppose that we have numbers between 1 and 500 in a binary search tree and want to search for the number 258. Which of the following sequences could not be the sequence of nodes examined ?

A.453, 200, 448, 210, 363, 258
B.3, 240, 398, 256, 399, 258
C.458, 250, 357, 255, 355, 258
D.3, 390, 358, 257, 312, 258

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: B

The impossible sequence is 3, 240, 398, 256, 399, 258.

In a binary search each node examined narrows the range in which 258 must lie. Following this sequence:

3 is less than 258, go right: the range is now above 3.
240 is less than 258, go right: above 240.
398 is greater than 258, go left: between 240 and 398.
256 is less than 258, go right: between 256 and 398.
399 lies outside that range, so it cannot be the next node examined.

The other three sequences stay inside their shrinking ranges at every step; for example 453, 200, 448, 210, 363, 258 narrows to (200, 453), (200, 448), (210, 448), (210, 363), all containing 258.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Binary Search Trees Questions and Answers || Binary Search Trees MCQ Questions and Answers || Binary Search Trees GK Questions and Answers || Binary Search Trees GK MCQ Questions || Binary Search Trees Multiple Choice Questions and Answers || Binary Search Trees GK || GK on Binary Search Trees || Data Structures and Algorithms Questions and Answers || Data Structures and Algorithms MCQ Questions and Answers || Data Structures and Algorithms GK Questions and Answers || GK on Data Structures and Algorithms

Binary Search Trees Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications