BST Delete Operation in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What are the three main cases to consider when deleting a node in a Binary Search Tree (BST)?

1. Node to delete is a leaf (no children).<br>2. Node to delete has one child.<br>3. Node to delete has two children.

intermediate

In BST deletion, how do you handle deleting a node with two children?

Replace the node's value with its inorder successor (smallest value in right subtree) or inorder predecessor (largest value in left subtree), then delete that successor/predecessor node.

intermediate

Why do we use the inorder successor or predecessor when deleting a node with two children in a BST?

Because replacing with inorder successor or predecessor maintains the BST property by ensuring all left subtree values remain smaller and right subtree values remain larger.

beginner

What happens if you delete a leaf node in a BST?

The leaf node is simply removed by setting its parent's pointer to null, as it has no children.

beginner

In Go, what is the base case for the recursive BST delete function?

When the current node is nil (empty), return nil to stop recursion.

Which node do you replace a deleted node with when it has two children in a BST?

A Random node in the tree

B Inorder successor or inorder predecessor

C Root node

D Any leaf node

Replacing with inorder successor or predecessor keeps the BST properties intact.

What is the first step when deleting a node in a BST?

A Find the node to delete

B Replace the node with root

C Delete all children first

D Balance the tree

You must first find the node to delete by traversing the BST.

If a node to delete has only one child, what do you do?

A Replace with inorder successor

B Replace the node with root

C Delete the entire subtree

D Replace the node with its child

You replace the node with its single child to maintain BST structure.

What is the inorder successor of a node in a BST?

A Smallest node in the right subtree

B Largest node in the left subtree

C Root node

D Any leaf node

Inorder successor is the smallest node in the right subtree.

What does the BST delete function return when the node to delete is not found?

A Nil (no change)

B Error

C Root node

D New node

If node is not found, the function returns the root unchanged.

Explain the steps to delete a node with two children in a BST.

Think about maintaining BST order after deletion.

Describe how BST deletion handles nodes with zero, one, and two children.

Consider each case separately.