GATE CS Binary Search Trees questions

Which of the following statement(s) is/are TRUE for any binary search tree (BST) having $n$ distinct integers?

Suppose the values $10,-4,15,30,20,5,60,19$ are inserted in that order into an initially empty binary search tree. Let $T$ be the resulting binary search tree. The number of edges in the path from the node containing $19$ to the root node of $T$ is _________. (Answer in integer)

​​​​​​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 …

Suppose a binary search tree with $1000$ 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 $3^{\text{rd}}$ largest element of the tree is stored at index ______________ .

A binary search tree $T$ contains $n$ distinct elements. What is the time complexity of picking an element in $T$ that is smaller than the maximum element in $T$?

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?

In a balanced binary search tree with $n$ elements, what is the worst case time complexity of reporting all elements in range $[a,b]$? Assume that the number of reported elements is $k$.

Let $T$ be a binary search tree with $15$ nodes. The minimum and maximum possible heights of $T$ are: Note: The height of a tree with a single node is $0$.

The pre-order traversal of a binary search tree is given by $12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20$. Then the post-order traversal of this tree is

The number of ways in which the numbers $1, 2, 3, 4, 5, 6, 7$ can be inserted in an empty binary search tree, such that the resulting tree has height $6$, is _________. Note: The height of a tree with a single node is $0$.

What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

Which of the following is/are correct in order traversal sequence(s) of binary search tree(s)? $3, 5, 7, 8, 15, 19, 25$ $5, 8, 9, 12, 10, 15, 25$ $2, 7, 10, 8, 14, 16, 20$ $4, 6, 7, 9, 18, 20, 25$

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

Suppose we have a balanced binary search tree $T$ holding $n$ numbers. We are given two numbers $L$ and $H$ and wish to sum up all the numbers in $T$ that lie between $L$ and $H$. Suppose there are $m$ such numbers in $T$. If the tightest upper bound on the time to compute the sum is $O(n^a\log^bn+m^c\log^dn)$, the value of …

The preorder traversal sequence of a binary search tree is $30, 20, 10, 15, 25, 23, 39, 35, 42$. Which one of the following is the postorder traversal sequence of the same tree?

Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of $n$ nodes?

The worst case running time to search for an element in a balanced binary search tree with $n2^{n}$ elements is

What is the maximum height of any AVL-tree with $7$ nodes? Assume that the height of a tree with a single node is $0$.

You are given the postorder traversal, $P$, of a binary search tree on the $n$ elements $1, 2, \dots, n$. You have to determine the unique binary search tree that has $P$ as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?

How many distinct binary search trees can be created out of $4$ distinct keys?