Insertion and deletion in a BST
Filed under Accolite
Free read 2 of 3Confirm whether duplicate values are allowed (assume not) and if the tree needs self-balancing (standard BST suffices unless specified as AVL/Red-Black).
The question
Implement insertion and deletion operations in a Binary Search Tree (BST).
Constraints
- The BST property must be maintained after every operation.
- Values in the BST are unique.
Examples
- Input
- Insert 5, 3, 7 into an empty BST, then delete 3.
- Output
- Tree structure becomes root 5 with right child 7.
- Why
- Inserting maintains BST order. Deleting a node with no children simply removes it.
Approach
Confirm whether duplicate values are allowed (assume not) and if the tree needs self-balancing (standard BST suffices unless specified as AVL/Red-Black).
Not applicable; tree operations are inherently structural pointers manipulations.
For insertion, traverse left or right recursively or iteratively based on comparison with the current node value. For deletion, handle three cases: leaf node, one child, or two children by replacing the node's value with its in-order successor and deleting the successor.
Deleting the root node, inserting into an empty tree, or deleting a value not present in the tree.
Solution
O(h) time where h is height, O(h) space for recursion stack
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if not root:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
return root
def deleteNode(root, key):
if not root:
return root
if key < root.key:
root.left = deleteNode(root.left, key)
elif key > root.key:
root.right = deleteNode(root.right, key)
else:
if not root.left:
return root.right
elif not root.right:
return root.left
curr = root.right
while curr.left:
curr = curr.left
root.key = curr.key
root.right = deleteNode(root.right, curr.key)
return root
Tips
- What they are testing: Test deleting a leaf node, a node with one child, and a node with two children (requiring successor/predecessor finding).
- Common mistake: Forgetting to handle the case where the deleted node has two children, where you must find the in-order successor in the right subtree.
Related Accolite questions
Collected from public candidate posts and coding forums. Updated Nov 2026.