Virtual Labs

1. What is the worst-case time complexity of searching for a key in a binary search tree containing

n

nodes?

O(n^2)

Explanation

O(n\log n)

Explanation

O(n)

Explanation

O(\log n)

Explanation

2. What is the worst-case time complexity of deleting a key from a binary search tree containing

n

nodes?

O(n^2)

Explanation

O(n\log n)

Explanation

O(n)

Explanation

O(\log n)

Explanation

3. What is the time complexity of deleting a key from a balanced binary search tree containing

n

nodes?

O(n^2)

Explanation

O(n\log n)

Explanation

O(n)

Explanation

O(\log n)

Explanation

4. If all the queries in a BST-based application occur after all insertions and deletions are complete, which approach can be faster for answering the subsequent search queries?

a: Sorting the keys and using binary search Explanation

Explanation

b: Sorting the keys and using only linear search Explanation

Explanation

c: Using binary search followed by another BST construction Explanation

Explanation

d: Using a stack for every search Explanation

Explanation

5. What is the best-case time complexity of searching for a key in a BST when the key is stored at the root?

O(1)

Explanation

O(\log n)

Explanation

O(n)

Explanation

O(n^2)

Explanation

6. What is the space complexity of a recursive BST search in the worst case, considering the recursion stack?

O(1)

Explanation

O(\log n)

Explanation

O(n)

Explanation

O(n^2)

Explanation

7. If a BST has height

h

, what is the time complexity of searching for a key in terms of

h

O(1)

Explanation

O(h)

Explanation

O(h^2)

Explanation

O(2^h)

Explanation

8. A balanced BST has height

O(\log n)

. What is the resulting time complexity of searching, inserting, or deleting a key when the required operation follows a root-to-leaf path?

O(1)

Explanation

O(n)

Explanation

O(n\log n)

Explanation

O(\log n)

Explanation

9. Which factor primarily determines the time complexity of basic search, insertion, and deletion operations in a binary search tree?

a: The number of leaves only Explanation

Explanation

b: The height of the tree Explanation

Explanation

c: The value stored at the root Explanation

Explanation

d: The number of pointers in each node Explanation

Explanation

Binary Search Tree