Deletion in BST in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Binary Search Tree (BST)?

A BST is a tree data structure where each node has at most two children. The left child's value is less than the parent node's value, and the right child's value is greater. This property helps in fast searching, insertion, and deletion.

beginner

What are the three main cases when deleting a node in a BST?

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

beginner

How do you delete a leaf node in a BST?

Simply remove the leaf node from the tree by updating its parent's pointer to null.

intermediate

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

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

intermediate

How do you delete a node with two children in a BST?

Find the node's inorder successor (smallest node in right subtree) or inorder predecessor (largest node in left subtree). Replace the node's value with that successor/predecessor's value, then delete the successor/predecessor node which will have at most one child.

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

A Find the inorder successor or predecessor

B Remove the node immediately

C Replace the node with a leaf node

D Swap the node with its parent

When deleting a node with two children, you first find the inorder successor or predecessor to replace the node's value.

If a node to delete has no children, what happens?

A The entire tree is restructured

B It is replaced by its child

C Its value is swapped with the root

D It is simply removed

A leaf node can be removed directly by updating its parent's pointer to null.

When deleting a node with one child, what is done?

A The node is replaced by its child

B The node is deleted and replaced by null

C The node is swapped with its sibling

D The node is left unchanged

The node is replaced by its single child to maintain the BST structure.

Which property must remain true after deleting a node in a BST?

A All nodes have two children

B Left child values are less than parent, right child values are greater

C The tree becomes a linked list

D All leaf nodes are at the same level

The BST property must be preserved after deletion to keep the tree ordered.

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

A The largest node in the left subtree

B The root node

C The smallest node in the right subtree

D The node's parent

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

Explain the three cases of deleting a node in a BST and how each case is handled.

Think about how the tree structure changes in each case.

Why is it important to find the inorder successor or predecessor when deleting a node with two children in a BST?

Consider what happens if you remove the node without replacement.