How to Delete a Node Binary Search Tree

Binary search trees are used to organize sequential data for easy retrieval. Each node in a binary search tree has between zero and two children. The left child for a node is always less than the node and the right child is always greater. Thus when we are searching for a specific node,we can compare our target to the current node. If our target is greater than the current node we continue searching down the right branch, if our target is less than the current node we search down the left branch. This provides a tremendous benefit in searching compared to stepping through an ordered list of these values. Deleting nodes from a binary tree is slightly more complicated than adding new nodes or finding old ones. Depending on the situation, we may have to rearrange the tree to ensure that the children of each node are still properly balanced.

Instructions

Deleting A Leaf Node

1. Verify that the node has no children.

2. Find the node's parent. Set the parent's child reference to null.

3. Remove the node from your storage array.

Deleting A Node With One Child

1. Verify that the node has only one child.

2. Find the node's parent. Set the parent's child reference to reference the child of the node you are deleting.

3. Remove the node from your storage array.

Deleting A Node With Two Children

1. Verify that the node has two children.

2. Find the greatest node in the tree to the left of the node (the predecessor). This can be done by stepping left in the tree one step, and then stepping right until there are no more right references.

3. Set the right reference of the predecessor to reference the right child of the node you are deleting.

4. Replace the parent node's reference to the predecessor.

5. Remove the node from your storage array.

Tips & Warnings

• Multiple deletions can cause your tree to become unbalanced. If you find that your program is running slowly after many deletions, you should program it to balance the tree on occasion.

References

• "Data Structures And Algorithms In Java"; Adam Drozdek; 2005
• Data Structures and File Management: Binary Trees