Deleting Nodes from a BST
There are three cases to consider in deleting a node from a binary
search tree.
- If the node is a leaf, just set its parent pointer to null and delete the node.
- If the node has just one child, point the "grandparent" to its child and delete the node.
- If the node has two children, find the node containing the "largest item" in the node's left subtree and swap the node's info with the "largest item" and revert to the first or second case
Redraw each binary search tree with the node containing N deleted.
Be sure to use the BST deletion algorithm explained above.
-
Challenge!
Add the function delete to the Tree Operations
Lab to delete a requested integer.
Continue to: Unit 8 / Prev / Next