Binary Search Tree

1. If a node in a binary search tree has two children, how can its value be deleted using its inorder successor?

a: Swap its value with the rightmost node in its left subtree, then delete the original node without reconnecting the tree. Explanation

Explanation

b: Swap its value with the leftmost node in its right subtree, then delete that successor node. Explanation

Explanation

c: Swap its value with the rightmost node in its left subtree, then delete the original node position without further changes. Explanation

Explanation

d: Swap its value with the leftmost node in its right subtree, then delete the root of the entire tree. Explanation

Explanation

2. If a node in a BST has only one child to the right and no left child, how can the node be deleted?

a: Swap its value with the leftmost node in its right subtree, then delete that node. Explanation

Explanation

b: Connect the node's parent directly to its right child, then delete the node. Explanation

Explanation

c: Delete the node and set all pointers to null. Explanation

Explanation

d: Swap its value with the root of the tree and then delete the root. Explanation

Explanation

3. In a real BST, deletion takes

O(\log n)

time when the tree is balanced. Assume an oracle can search and compute the minimum or maximum of a subtree in

O(1)

time. What is the time complexity of an optimal deletion algorithm using this oracle?

O(1)

Explanation

O(\log n)

Explanation

O(\log(\log n))

Explanation

O(n)

Explanation

4. When deleting a leaf node from a BST, what should be done?

a: Replace it with its inorder successor. Explanation

Explanation

b: Replace it with its inorder predecessor. Explanation

Explanation

c: Remove the node and update its parent's corresponding child pointer. Explanation

Explanation

d: Replace it with the root. Explanation

Explanation

5. Which node can be used to replace a BST node that has two children while preserving the BST ordering property?

a: Any leaf in the tree Explanation

Explanation

b: The inorder successor or inorder predecessor Explanation

Explanation

c: The root only Explanation

Explanation

d: Any node at the same level Explanation

Explanation

6. Which of the following cases is generally the simplest BST deletion case?

a: Deleting a node with two children Explanation

Explanation

b: Deleting the root when it has two children Explanation

Explanation

c: Deleting a leaf node Explanation

Explanation

d: Deleting a node whose successor has a child Explanation

Explanation

7. When deleting a BST node using its inorder successor, where is that successor located?

a: At the leftmost node of the target's right subtree Explanation

Explanation

b: At the rightmost node of the target's right subtree Explanation

Explanation

c: At the leftmost node of the target's left subtree Explanation

Explanation

d: At the root of the entire tree Explanation

Explanation

8. After replacing a BST node with its inorder successor, why is deleting the successor usually simpler than deleting the original two-child node?

a: The successor is always the root. Explanation

Explanation

b: The successor is guaranteed to have no parent. Explanation

Explanation

c: The successor has no larger keys in the tree. Explanation

Explanation

d: The inorder successor has no left child and therefore has at most one child. Explanation

Explanation

9. If a BST node has only a left child, what is the appropriate structural action when deleting that node?

a: Connect the parent directly to the left child. Explanation

Explanation

b: Delete the entire left subtree. Explanation

Explanation

c: Replace the node with the root of the tree. Explanation

Explanation

d: Always rotate the tree before deletion. Explanation

Explanation