BST Insert and Remove
Implementing insertion and deletion in binary search trees. Handle all deletion cases including nodes with two children.
Insertion and deletion in Binary Search Trees must maintain the BST property. Insertion is straightforward, but deletion has several cases to handle.
BST Insertion
To insert a value:
- If tree is empty, create root
- Otherwise, find the correct position by comparing with each node
- Insert as a leaf
def insert(self, val):
if self.root is None:
self.root = TreeNode(val)
else:
self._insert(self.root, val)
def _insert(self, node, val):
if val < node.val:
if node.left is None:
node.left = TreeNode(val)
else:
self._insert(node.left, val)
else: # val >= node.val
if node.right is None:
node.right = TreeNode(val)
else:
self._insert(node.right, val)
Inserting 5 into BST:
8 8
/ \ / \
3 10 3 10
/ \ / \
1 6 → 1 6
/ \
5 (existing subtree)
5 < 8 → go left
5 > 3 → go right
5 < 6 → go left
6.left is None → insert here
Iterative Insert
def insert_iterative(self, val):
new_node = TreeNode(val)
if self.root is None:
self.root = new_node
return
parent = None
current = self.root
while current:
parent = current
if val < current.val:
current = current.left
else:
current = current.right
if val < parent.val:
parent.left = new_node
else:
parent.right = new_node
BST Deletion
Deletion is more complex. There are three cases:
Case 1: Deleting a Leaf
Simply remove the node.
Delete 4:
8 8
/ \ / \
3 10 3 10
/ \ / \
1 6 → 1 6
/
4 (4 removed)
Case 2: Node with One Child
Replace the node with its child.
Delete 6 (has left child 4):
8 8
/ \ / \
3 10 3 10
/ \ / \
1 6 → 1 4
/
4
Case 3: Node with Two Children
Replace with either:
- Inorder successor: Smallest node in right subtree
- Inorder predecessor: Largest node in left subtree
Then delete the successor/predecessor.
Delete 3 (has two children):
8 8
/ \ / \
3 10 4 10
/ \ / \
1 6 → 1 6
/
4
Inorder successor of 3 is 4.
Replace 3 with 4, delete original 4.
Complete Delete Implementation
def delete(self, val):
self.root = self._delete(self.root, val)
def _delete(self, node, val):
if node is None:
return None
# Find the node to delete
if val < node.val:
node.left = self._delete(node.left, val)
elif val > node.val:
node.right = self._delete(node.right, val)
else:
# Found the node to delete
# Case 1 & 2: No child or one child
if node.left is None:
return node.right
if node.right is None:
return node.left
# Case 3: Two children
# Find inorder successor (smallest in right subtree)
successor = self._find_min(node.right)
# Copy successor's value to this node
node.val = successor.val
# Delete the successor
node.right = self._delete(node.right, successor.val)
return node
def _find_min(self, node):
while node.left:
node = node.left
return node
func (bst *BST) Delete(val int) {
bst.root = deleteNode(bst.root, val)
}
func deleteNode(node *TreeNode, val int) *TreeNode {
if node == nil {
return nil
}
if val < node.Val {
node.Left = deleteNode(node.Left, val)
} else if val > node.Val {
node.Right = deleteNode(node.Right, val)
} else {
// Found node to delete
if node.Left == nil {
return node.Right
}
if node.Right == nil {
return node.Left
}
// Two children: find successor
successor := findMin(node.Right)
node.Val = successor.Val
node.Right = deleteNode(node.Right, successor.Val)
}
return node
}
func findMin(node *TreeNode) *TreeNode {
for node.Left != nil {
node = node.Left
}
return node
}
Successor vs Predecessor
You can use either the inorder successor (min of right subtree) or inorder predecessor (max of left subtree) for case 3. The choice is arbitrary, but being consistent simplifies debugging.
Visualizing Case 3
Delete 8 (root with two children):
Original:
8
/ \
3 10
/ \ / \
1 6 9 14
Inorder successor of 8 is 9 (min of right subtree)
Step 1: Copy 9's value to 8's position
9
/ \
3 10
/ \ / \
1 6 9 14
Step 2: Delete original 9 (it's a leaf or has one child)
9
/ \
3 10
/ \ \
1 6 14
Iterative Delete
def delete_iterative(self, val):
parent = None
current = self.root
# Find the node and its parent
while current and current.val != val:
parent = current
if val < current.val:
current = current.left
else:
current = current.right
if current is None:
return # Value not found
# Case 1 & 2: At most one child
if current.left is None or current.right is None:
child = current.left if current.left else current.right
if parent is None:
self.root = child
elif parent.left == current:
parent.left = child
else:
parent.right = child
# Case 3: Two children
else:
# Find inorder successor
succ_parent = current
successor = current.right
while successor.left:
succ_parent = successor
successor = successor.left
# Copy successor value
current.val = successor.val
# Delete successor
if succ_parent.left == successor:
succ_parent.left = successor.right
else:
succ_parent.right = successor.right
Building a BST from Array
def build_bst(arr):
bst = BST()
for val in arr:
bst.insert(val)
return bst
# Order matters!
arr1 = [5, 3, 7, 2, 4, 6, 8] # Balanced
arr2 = [2, 3, 4, 5, 6, 7, 8] # Skewed (sorted input)
To build a balanced BST from sorted array:
def sorted_array_to_bst(arr):
if not arr:
return None
mid = len(arr) // 2
root = TreeNode(arr[mid])
root.left = sorted_array_to_bst(arr[:mid])
root.right = sorted_array_to_bst(arr[mid + 1:])
return root
Insertion Order Matters
Inserting sorted data creates a skewed tree (linked list). To get a balanced tree, either insert in random order, use a balanced tree variant, or build from sorted array using the middle element as root.
Complete BST Class
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, val):
if self.root is None:
self.root = TreeNode(val)
else:
self._insert(self.root, val)
def _insert(self, node, val):
if val < node.val:
if node.left is None:
node.left = TreeNode(val)
else:
self._insert(node.left, val)
else:
if node.right is None:
node.right = TreeNode(val)
else:
self._insert(node.right, val)
def search(self, val):
return self._search(self.root, val)
def _search(self, node, val):
if node is None or node.val == val:
return node
if val < node.val:
return self._search(node.left, val)
return self._search(node.right, val)
def delete(self, val):
self.root = self._delete(self.root, val)
def _delete(self, node, val):
if node is None:
return None
if val < node.val:
node.left = self._delete(node.left, val)
elif val > node.val:
node.right = self._delete(node.right, val)
else:
if node.left is None:
return node.right
if node.right is None:
return node.left
successor = node.right
while successor.left:
successor = successor.left
node.val = successor.val
node.right = self._delete(node.right, successor.val)
return node
def inorder(self):
result = []
self._inorder(self.root, result)
return result
def _inorder(self, node, result):
if node:
self._inorder(node.left, result)
result.append(node.val)
self._inorder(node.right, result)
Time Complexity
| Operation | Balanced | Skewed | |-----------|----------|--------| | Insert | O(log n) | O(n) | | Delete | O(log n) | O(n) | | Search | O(log n) | O(n) |
Key Takeaways
- Insert: Find correct position using BST property, add as leaf
- Delete has three cases: leaf, one child, two children
- Two-child deletion uses inorder successor or predecessor
- Insertion order affects tree balance
- Sorted input creates worst-case O(n) height
- Build balanced tree from sorted array using middle element
Understanding BST insert and delete operations is essential before moving to self-balancing trees like AVL and Red-Black trees, which automate maintaining balance.