SW11: Binary Search Tree - BST

Question 1

What is the key feature that distinguishes a Binary Search Tree (BST) from a regular Binary Tree?
A. It uses fewer pointers per node.
B. It must be perfectly balanced.
C. It only allows keys of integer type.
D. It enforces an ordering on the keys, where all left keys are smaller and all right keys are larger.

Answer 1

D. It enforces an ordering on the keys, where all left keys are smaller and all right keys are larger.

Question 2

What is the space complexity of a recursive in-order traversal on a perfectly balanced BST with n nodes?
A. O(1)
B. O(n)
C. O(logn)
D. O(n^2)

Answer 2

C. O(logn)

Question 3

How does a findMin (or minValueNode) function typically find the minimum value node in a given BST subtree?
A. It traverses once to the rightmost node.
B. It searches the entire subtree for the smallest value.
C. It traverses as far left as possible.
D. It compares the key of the root to the keys of its children.

Answer 3

C. It traverses as far left as possible.

Question 4

What is the fundamental rule of a Binary Search Tree (BST) that must be true for all nodes in the tree?
A. The tree must be complete (all levels full).
B. The height must not exceed logn.
C. All nodes in the left subtree must be less than the node, and all nodes in the right subtree must be greater.
D. The parent’s key must be greater than both children’s keys.

Answer 4

C. All nodes in the left subtree must be less than the node, and all nodes in the right subtree must be greater.

Question 5

What is the correct procedure for deleting a BST node that has only one child?
A. The node is simply deleted, and the child becomes a leaf.
B. The node is deleted, and its child is moved to the root of the tree.
C. The algorithm searches for a replacement from a different subtree.
D. The algorithm promotes the single child node to replace the deleted node, linking the child to the deleted node’s parent.

Answer 5

D. The algorithm promotes the single child node to replace the deleted node, linking the child to the deleted node’s parent.

Question 6

What is the time complexity for the standard tree traversal methods (pre-order, in-order, post-order) on a tree with n nodes?
A. O(logn)
B. O(n)
C. O(n^2)
D. O(nlogn)

Answer 6

B. O(n)

Question 7

You are given an empty BST. You insert the following keys in this order: 10, 15, 12, 11. Where will the 11 node be placed?
A. As the right child of 15.
B. As the right child of 10.
C. As the right child of 11.
D. As the left child of 12.

Answer 7

D. As the left child of 12.

Question 8

What is the standard base case for a recursive function designed to calculate the height of a BST?
A. If the current node is a leaf, return 1.
B. If the current node is None (or null), return 0.
C. If the current node is the root, return 0.
D. If the current node has no children, return -1.

Answer 8

B. If the current node is None (or null), return 0.

Question 9

What is the time complexity of a search operation in a worst-case (completely unbalanced) BST with ‘n’ nodes?
A. O(logn)
B. O(1)
C. O(nlogn)
D. O(n) (Linear)

Answer 9

D. O(n) (Linear)

Question 10

The in-order traversal of a Binary Search Tree (BST) will output the keys in ascending order.

Answer 10

True

Question 11

If you delete a leaf node in a BST, the parent node’s reference to it is set to None (or null).

Answer 11

True

Question 12

If you delete the root node 20 (Left: 10, Right: 30, 30’s Left: 25) using the in-order successor for replacement, what value will be at the root?
A. 10
B. 30
C. 25
D. The tree will become empty.

Answer 12

C. 25

Question 13

What is the in-order successor (used for deletion)?
A. The key of the largest node in its left subtree.
B. The key of the parent node.
C. The key of the node immediately following it in the array representation.
D. The key of the smallest node in its right subtree.

Answer 13

D. The key of the smallest node in its right subtree.

Question 14

The delete operation in a BST is a leaf-first approach, where the actual deletion always happens at a leaf node.

Answer 14

True

Question 15

What is the main purpose of the findMin operation in the context of BST deletion?
A. To find the key of the node to be deleted.
B. To find the parent of the node to be deleted.
C. To ensure the tree remains balanced after deletion.
D. To find the in-order successor.

Answer 15

D. To find the in-order successor.

Question 16

If you check the balance factor at every node after an insertion, what is the overall complexity of a non-self-balancing BST insertion?
A. O(logn)
B. O(nlogn)
C. O(n)
D. O(n^2)

Answer 16

O(n^2)

Question 17

A balanced BST guarantees that all search operations will be O(log n).

Answer 17

TRUE

Question 18

A completely unbalanced binary search tree is analogous to a(n) _____.

Answer 18

Linked list