BST Delete Operation in DSA Javascript - 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 the current node.

intermediate

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

Because it maintains the BST property by ensuring all left subtree nodes are smaller and all right subtree nodes are larger than the replaced node.

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.

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 one child

C Node has three children

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 Parent node

The inorder successor (smallest node in right subtree) is used to replace the deleted node to maintain BST properties.

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

A Smallest node in right subtree

B Parent node

C Largest node in left subtree

D Any leaf node

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 inorder successor

B Remove the node and connect its child directly to its parent

C Replace node with inorder predecessor

D Do nothing

The node is removed and its single child is linked directly to the node's parent.

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

A BST becomes empty

B BST property is broken

C BST becomes a linked list

D BST property is maintained

Replacing with inorder successor maintains the BST property because the successor fits correctly in the tree order.

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

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 connections between nodes.