Binary search tree Binary Previous Year Questions for GATE

In this article, we'll discuss some previous year's questions about Binary Search Trees along with the explanation of the answers.

Top MCQs on Binary Search Tree Data Structure with Answers

Question 1: In a generic Binary Search Tree, what is the worst-case time complexity for search, insert, and delete operations?

1. O(n) for delete and O(Logn) for search and insert
2. O(Logn) for all the operations
3. O(n) for insert and delete, O(Logn) for search
4. O(n) for all the operations

Answer : D

In the Worst case, we can expect to have a skew tree means a tree with all the nodes having only one child for example this tree

In such a type of tree, you need to iterate on all the nodes to perform any operation which will always cost linear time complexity.

Question 2: The height of a tree is determined by finding the longest path from the root to the leaf node. The maximum and the minimum number of nodes in a binary tree of height 4 are:

1. 31 and 5, respectively
2. 64 and 5, respectively
3. 32 and 6, respectively
4. 31 and 5, respectively

Answer: A

The number of nodes in a tree will be maximum if it is a perfect binary tree.

A perfect binary tree of height h has 2^(h+1) - 1 node

So putting h in the formula will give 31 as the answer

The number of nodes will be minimum for a skewed binary tree.

A perfect binary tree of height h has h+1 nodes.

So putting h in the formula will give 5 as the answer

Question 3: Which traversal of a tree will give the elements in sorted order for a Binary search tree.

1. Postorder
2. Preorder
3. Level order
4. Inorder

Answer: D

In binary search tree, elements in the left side are smaller than the right side, and in inorder traversal, while moving from left to right elements will always be given in sorted order.

Question 4: From given traversals Which of these is sufficient to construct BST

1) Inorder 2) Preorder 3) Postorder

1. Any one of the given three traversals is sufficient
2. 2 and 3
3. Either 2 or 3 is sufficient
4. 1 and 3

Answer: C

We can build the BST if we know either preorder or postorder traversal. It's worth noting that the inorder traversal may always be obtained by sorting the supplied traversal. BST's inorder traversal is always ordered.
Question 5: Consider these two statements

Statement 1: A binary tree X is full if each node is either a leaf or possesses exactly two child nodes.

Statement 2: A binary tree T with n levels is complete if all levels except possibly the last are completely full, and the last level has all its nodes to the left side. Which statement is/are TRUE

1. Only 1
2. Only 2
3. Both 1 and 2
4. Neither 1 nor 2

Answer: C

Both statements are true because it is the definition of a full binary search tree that it is a perfect binary search tree.

Question 6: There are n unique elements in a binary search tree Tree. What is the time complexity of selecting an element in a Tree that is smaller than the maximum element in the Tree?

1. Θ(n)
2. Θ(nlogn)
3. Θ(1)
4. Θ(logn)

Answer: C

If an element in a binary search tree is smaller than any particular element in the binary search tree then it is for sure smaller than the maximum element in the binary search tree and all the elements in the binary search tree are different. Hence comparing only two elements will cost constant time complexity.

Question 7: In the delete operation of a Binary search tree, we need an inorder successor of a tree node when the tree node to be deleted has both left and right children as not null. Then which of the following options is true about the inorder successor needed in delete operation?

1. In order, the successor will always be either a leaf node or a node with always be an empty left child
2. In order, Successor will always be a leaf node
3. Inorder successor may be an ancestor of the node
4. In order, successor is always either a leaf node or a node with an empty right child Binary Search Trees    

Answer: C

Let T be the Tree node that has to be deleted in a Binary search tree with root as 'rootNode'. There are three possibilities for the deletion Let's explore all the cases

case 1) If T is a leaf node then We can change the left or right pointer of the parent to NULL (depending upon whether T is the left child or right child of its parent node) and we delete T 

case 2) One child of T is null then We can copy the values of the non-empty child to T and then we can delete the non-empty child

case 3) Both children of T are non-null: In that scenario, we can find the inorder successor of T. Let the inorder successor be Z then We can copy the contents of Z to T, and can delete Z. we need an inorder successor only when both left and right child of T is not null. 

Question 8: You are given a set of n different elements and an unlabelled binary tree with a total of n nodes. Find the total number of ways to populate the tree with the given set so that it becomes a binary search tree? (GATE CS 2011)

1. 1
2. 0
3. n!
4. (1/(n+1)).2nCn

Answer: A

There is only one way. For the minimum value, we need to go to the leftmost node and for the maximum value, we need to the rightmost node. Recursively, we can define for other nodes also.

Question 9: Assume the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in an empty binary search tree. The binary search tree employs the standard natural number ordering. Then from the above options choose the best in-order traversal sequence of the resultant tree?

1. 0 1 2 3 4 5 6 7 8 9
2. 9 8 6 4 2 3 0 1 5 7
3. 5 1 7 6 8 3 4 0 9 2
4. 7 5 1 0 3 2 4 6 8 9

Answer: A

As explained in question 3 above the binary search tree elements are printed in sorted order if we do inorder traversal hence option a is correct.

Question 10: Given below are the numbers and these are inserted into an empty binary search tree in the following order: 10, 1, 3, 5, 15, 12, 16. Find the height of the binary search tree formed from the given numbers(the height of a Tree is the maximum distance of a leaf node from the root)? (GATE CS 2004)

1. 4
2. 2
3. 3
4. 6

Answer: C

After construction of the binary search tree, it will look like this, and hence the height of the tree is 3.

Conclusion

In this article, we have extensively discussed the important questions from the binary search tree and some previously asked questions in the gate exam.

Recommended problems -

• Binary Array Sorting
• Vertical Order Traversal of a Binary Tree
• Leaf Nodes in Binary Tree
• Root To Leaf Path

Until then, All the best for your future endeavors, and Keep Coding. "We hope that this blog has helped you enhance your knowledge regarding this problem, and if you would like to learn more, check out our articles on  Code 360. Do upvote our blog to help other ninjas grow. Happy Coding!”