Insertion and Deletion
Explore the core operations of insertion and deletion in binary search trees (BST). Learn the step-by-step algorithms for adding and removing nodes, including handling cases like leaf nodes and nodes with one or two children. Understand the importance of preserving BST properties and the impact on time and space complexity. This lesson helps you implement these operations efficiently in Java and prepares you to manage dynamic tree structures.
We'll cover the following...
Insertion and deletion are two of the most important operations in a binary search tree (BST). Whenever we insert or delete a node, we must make sure that the BST property remains true:
All values in the left subtree are smaller than the node.
All values in the right subtree are greater than or equal to the node.
If this ordering rule is preserved, the tree remains a valid BST.
Insertion
To insert a value into a BST, we begin at the root and compare the new value with the current node.
If the new value is smaller, we move to the left child.
If the new value is greater than or equal to, we move to the right child.
We continue this process until we find an empty position.
The new node is inserted there.
This works because every comparison tells us exactly which direction to move.
Example of insertion
For example, suppose we start with this BST:
If we insert
, so move right , so move left , so move right
The new node is inserted as the right child of