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.

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

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