GATE CSE concept:binary-search-trees PYQs & Answers

Questions 1–10 of 13. Imported answers require independent review unless marked reviewed.

Let

be the set of all integers from 1 to 15. Consider any order of insertion of the elements of

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?

Your answerChoose one option.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider a binary search tree (BST) with

leaf nodes (

). Given any node

, the key present in the node is denoted as

. All the keys present in the given BST are distinct. The keys belong to the set of real numbers.

For a node

, let

denote the node that is its inorder successor. If a node

does not have an inorder successor, then

. As there are no duplicates, if

is not

, then

Corresponding to every leaf node

that has a non-NULL

, a new key

with the following property is to be inserted into the BST.

Let

represent the list of all such new keys to be inserted into the BST.

Which of the following statements is/are true?

Your answerSelect all correct options. You can choose more than one.

cannot have any duplicates

will have at least one element

After inserting all keys from

, the height of the BST can increase at most by one

Number of nodes in the BST will double after inserting all keys from

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

The following sequence corresponds to the preorder traversal of a binary search tree

50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77

The position of the element 60 in the postorder traversal of

is _____. (answer in integer)

Note: The position begins with 1.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Which of the following statement(s) is/are TRUE for any binary search tree (BST) having

distinct integers?

Your answerSelect all correct options. You can choose more than one.

The maximum length of a path from the root node to any other node is

An inorder traversal will always produce a sorted sequence of elements.

Finding an element takes

time in the worst case.

Every BST is also a Min-Heap.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Suppose the values 10, −4, 15, 30, 20, 5, 60, 19 are inserted in that order into an initially empty binary search tree. Let

be the resulting binary search tree. The number of edges in the path from the node containing 19 to the root node of

is __________. (Answer in integer)

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures:

P: Unsorted doubly linked list with pointers to the head node and tail node of the list.

Q: Min-heap implemented using an array.

R: Binary Search Tree.

Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size

of these data structures?

Your answerChoose one option.

, Q:

, R:

, Q:

, R:

, Q:

, R:

, Q:

, R:

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

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?

Your answerChoose one option.

Inorder traversal of T can be determined from V

Root node of T can be determined from V

Preorder traversal of T can be determined from V

Postorder traversal of T can be determined from V

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Suppose a binary search tree with 100 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index ____________.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

A binary search tree

contains

distinct elements. What is the time complexity of picking an element in

that is smaller than the maximum element in

Your answerChoose one option.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19.

Which one of the following is the postorder traversal of the tree?

Your answerChoose one option.

10, 11, 12, 15, 16, 18, 19, 20

11, 12, 10, 16, 19, 18, 20, 15

20, 19, 18, 16, 15, 12, 11, 10

19, 16, 18, 20, 11, 12, 10, 15

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

GATE CSE concept:binary-search-trees PYQs

How to practice concept:binary-search-trees

Question 40

Question 49

Question 62

Question 26

Question 35

Question 38

Question 39

Question 28

Question 10

Question 5