Insertion and Deletion

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 $65$, we compare step by step:

• $65 > 50$, so move right

• $65 < 70$, so move left

• $65 > 60$, so move right

The new node is inserted as the right child of ...