Virtual Labs

1. Following is the image of a binary search tree rooted at 4.

Which of the following can be the sequence of nodes visited when searching for 10, assuming that 10 is not present in the tree?

a: 4, 6, 7, 10 Explanation

Explanation

b: 4, 6, 7, 8 Explanation

Explanation

c: 4, 3, 1, 2 Explanation

Explanation

d: 4, 6, 5, 10 Explanation

Explanation

2. To find the smallest element in the subtree rooted at a given node, we:

a: Go recursively into the left child of the current node and stop when no left child exists. Explanation

Explanation

b: Go recursively into the left child, then go right if possible, and stop when neither child exists. Explanation

Explanation

c: Go recursively into the right child of the current node and stop when no left child exists. Explanation

Explanation

d: Go recursively into the right child and stop when neither child exists. Explanation

Explanation

3. When searching for a key

x

in a BST, if the current node contains a key smaller than

x

, which child should be examined next?

a: Left child Explanation

Explanation

b: Right child Explanation

Explanation

c: Both children Explanation

Explanation

d: The parent Explanation

Explanation

4. If the key being searched for is equal to the key at the current node, what should a standard BST search do?

a: Continue to the left subtree Explanation

Explanation

b: Continue to the right subtree Explanation

Explanation

c: Report that the key has been found Explanation

Explanation

d: Restart from the root Explanation

Explanation

5. What happens when a BST search reaches a null child pointer before finding the target key?

a: The search is unsuccessful Explanation

Explanation

b: The root is automatically inserted again Explanation

Explanation

c: The search becomes a linear search Explanation

Explanation

d: The target is assumed to be present Explanation

Explanation

6. A BST contains the keys 50, 30, 70, 20, 40, 60, and 80. What is the search path for key 60?

a: 50, 30, 40, 60 Explanation

Explanation

b: 50, 70, 60 Explanation

Explanation

c: 50, 70, 80, 60 Explanation

Explanation

d: 50, 30, 20, 60 Explanation

Explanation

7. In a BST, where is the largest key in a subtree located?

a: At the leftmost node Explanation

Explanation

b: At the root of the subtree Explanation

Explanation

c: At the rightmost node Explanation

Explanation

d: At the deepest leaf Explanation

Explanation

8. What is the worst-case time complexity of searching for a key in an unbalanced BST containing

n

nodes?

O(1)

Explanation

O(\log n)

Explanation

O(n)

Explanation

O(n^2)

Explanation

9. A BST has root 40. During a search for 35, the search moves from 40 to 20. Which subtree of 20 should be searched next?

a: Left subtree Explanation

Explanation

b: Right subtree Explanation

Explanation

c: Both subtrees Explanation

Explanation

d: The subtree rooted at 40 Explanation

Explanation

Binary Search Tree