Deletion in BST in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the node to delete in a BST.

Data Structures Theory

if key < root.val:
    root.left = deleteNode(root.left, [1])
else:
    root.right = deleteNode(root.right, key)

Drag options to blanks, or click blank then click option'

Aroot.val

Broot.left

Ckey

Droot.right

Attempts:

3 left

💡 Hint

Common Mistakes

Using root.val instead of key in the recursive call.

Passing root.left instead of key as the argument.

To delete a node, we compare the key with the current node's value. If the key is smaller, we move to the left subtree by calling deleteNode with the key.

2fill in blank

medium

Complete the code to find the minimum value node in the right subtree during deletion.

Data Structures Theory

def minValueNode(node):
    current = node
    while current.[1] is not None:
        current = current.left
    return current

Drag options to blanks, or click blank then click option'

Aright

Bleft

Cval

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Checking current.right instead of current.left.

Returning current before the loop.

The minimum value node in a BST is found by going as far left as possible.

3fill in blank

hard

Fix the error in the code that replaces the node's value with the inorder successor's value.

Data Structures Theory

temp = minValueNode(root.[1])
root.val = temp.val
root.[2] = deleteNode(root.right, temp.val)

Drag options to blanks, or click blank then click option'

Aleft

Bright

Cparent

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Using root.left instead of root.right.

Deleting from the wrong subtree.

The inorder successor is the minimum node in the right subtree, so we must look at root.right and delete from root.right.

4fill in blank

hard

Fill both blanks to handle the case when the node to delete has only one child.

Data Structures Theory

if root.left is None:
    return root.[1]
elif root.[2] is None:
    return root.left

Drag options to blanks, or click blank then click option'

Aright

Bleft

Cval

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Returning root.left when left is None.

Checking root.val instead of root.left or root.right.

If the left child is missing, return the right child. If the right child is missing, return the left child.

5fill in blank

hard

Fill all three blanks to complete the deletion function for a BST.

Data Structures Theory

def deleteNode(root, key):
    if root is None:
        return root
    if key < root.val:
        root.left = deleteNode(root.left, [1])
    elif key > root.val:
        root.right = deleteNode(root.right, [2])
    else:
        if root.left is None:
            return root.[3]
        elif root.right is None:
            return root.left
        temp = minValueNode(root.right)
        root.val = temp.val
        root.right = deleteNode(root.right, temp.val)
    return root

Drag options to blanks, or click blank then click option'

Akey

Broot.val

Croot.left

Droot.right

Attempts:

3 left

💡 Hint

Common Mistakes

Passing root.val instead of key in recursive calls.

Returning root.left when left is None.

When searching for the node to delete, we pass the key down the tree. If the left child is missing, we return the right child.