BST Delete Operation in DSA Typescript - 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.

beginner

What is the inorder successor in a BST?

The node with the smallest value in the right subtree of a given node.

intermediate

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

To maintain the BST property where left subtree nodes are smaller and right subtree nodes are larger than the node, ensuring the tree remains correctly ordered after deletion.

beginner

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

You simply remove the leaf node by setting its parent's pointer to null, as it has no children.

Which of the following is NOT a case to consider when deleting a node in a BST?

A Node has no children

B Node has three children

C Node has one child

D Node has two children

In a BST, a node can have at most two children, so 'three children' is not a valid case.

When deleting a node with two children, which node is commonly used to replace it?

A Inorder successor

B Root node

C Random leaf node

D Inorder predecessor

The inorder successor (smallest node in the right subtree) is commonly used to replace a node with two children.

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

A Any leaf node

B Largest node in left subtree

C Root node

D Smallest node in right subtree

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

If a node to delete has only one child, what is the deletion process?

A Replace node with its child

B Replace node with root

C Delete node and all children

D Replace node with inorder successor

If the node has one child, replace the node with its child to maintain BST structure.

What happens to the BST property after deleting a node and replacing it with its inorder successor?

A BST property is broken

B Tree becomes unbalanced

C BST property is maintained

D Tree becomes empty

Replacing with inorder successor maintains the BST property because the successor fits correctly in the node's position.

Explain the steps to delete a node with two children in a Binary Search Tree.

Think about how to keep the tree ordered after deletion.

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

Consider the number of children and how the tree links change.