BST Delete Operation in DSA C++ - 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 the inorder successor or predecessor maintains the BST property after replacement, ensuring the tree remains correctly ordered.

beginner

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

The leaf node is simply removed, and its parent's pointer to it is set to null.

beginner

How do you delete a node with only one child in a BST?

Replace the node with its single child by updating the parent's pointer to point to the child, then delete the node.

Which node do you replace a node with when deleting a node with two children in a BST?

A Root node

B Inorder successor or inorder predecessor

C Any leaf node

D Random node in the tree

The inorder successor or predecessor maintains the BST property after deletion.

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 the entire tree

D Swap left and right children

You must first find the node to delete before handling its removal.

If a node to delete has no children, what do you do?

A Replace it with inorder successor

B Replace it with its child

C Do nothing

D Remove the node and set parent's pointer to null

A leaf node can be removed directly by updating the parent's pointer.

When deleting a node with one child, what happens to the child?

A It becomes the root

B It is deleted too

C It replaces the deleted node

D It is moved to the leaf

The single child replaces the deleted node to maintain the BST structure.

Which traversal helps find the inorder successor in a BST?

A Right subtree's minimum node

B Right subtree's maximum node

C Left subtree's maximum node

D Left subtree's minimum node

The inorder successor is the smallest node in the right subtree.

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

Think about maintaining BST order after deletion.

Describe how deleting a node with one child differs from deleting a leaf node in a BST.

Focus on how the parent's pointer changes.