Virtual Labs

1. If a node has 2 children, how can we delete the value in that node:

a: By swapping it’s value with the rightmost node in it’s left subtree, then deleting that rightmost node. Explanation

Explanation

b: By swapping it’s value with the leftmost node in it’s right subtree. Explanation

Explanation

c: By swapping it’s value with the rightmost node in it’s left subtree, then deleting the node which originally contained the target value. Explanation

Explanation

d: By swapping it’s value with the leftmost node in it’s right subtree, then deleting the node which originally contained the target value. Explanation

Explanation

2. If a node has 1 child to the right, but not left child, how can we delete it:

a: By swapping it’s value with the leftmost node in it’s right subtree, then deleting that leftmost node. Explanation

Explanation

b: By assigning it’s child’s parent as it’s parent, by assigning it’s parents right child as it’s right child, and then deleting itself. Explanation

Explanation

c: By just deleting the target node and making the pointers null if they were pointing to the node being deleted. Explanation

Explanation

d: By swapping the value of this node with the root of the tree and then deleting the root node. Explanation

Explanation

3. In a real BST, delete takes O(log n) time. Assume that you discover an oracle which can search, compute min or max of a subtree, in a binary search tree in O(1) time. What will the time complexity of the optimal deletion algorithm using this oracle:

a: O(1) Explanation

Explanation

b: O(log n) Explanation

Explanation

c: O(log(log(n)) Explanation

Explanation

d: O(n) Explanation

Explanation

Binary Search Tree