Delete Node in a BST

Category

Binary Search Tree

Checkbox

Difficulty

Medium

Index

Key Ideas

The key idea to solve the problem "Delete Node in a BST" is to recursively find the target node to be deleted, and handle different cases based on the number of children the node has.

Problem Number

450

Problem Summary

# Delete Node in a BST Given a binary search tree (BST) and a key, delete the node with the given key from the BST. Return the root node of the modified BST. Key Pitfalls: - When the node to be deleted has two children, it is necessary to find the node with the next larger value (successor) or the node with the next smaller value (predecessor) to replace it. - Be careful with handling cases where the node to be deleted is the root node of the BST. - Pay attention to updating the parent pointers and reconnecting the child nodes correctly after deleting a node.

Solution Summary

The best solution to solve the "Delete Node in a BST" problem is as follows: 1. If the root is null, return null. 2. If the key to be deleted is less than the root's value, recursively call the function on the left subtree. 3. If the key to be deleted is greater than the root's value, recursively call the function on the right subtree. 4. If the key to be deleted is equal to the root's value, handle three cases: - If the root has no left child, return the right child. - If the root has no right child, return the left child. - If the root has both left and right children, find the minimum value in the right subtree, replace the root's value with the minimum value, and recursively delete the minimum value from the right subtree. 5. Return the modified root. By following these steps, the function effectively deletes the node with the given key from the binary search tree.