← Accolite questions

Insertion and deletion in a BST

Filed under Accolite

Free read 2 of 3

Confirm 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

  1. Confirm whether duplicate values are allowed (assume not) and if the tree needs self-balancing (standard BST suffices unless specified as AVL/Red-Black).

Solution

O(h) time where h is height, O(h) space for recursion stack

Python
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.