BST Operations: Search, Insert & Delete

The three core BST operations — search, insert, and delete — all exploit the same idea: at each node, the BST property tells you to go left or right, so you discard half the tree each step. That gives O(h) time: O(log n) on a balanced tree, O(n) on a skewed one.

We reuse the standard TreeNode.

Search

Compare the target with the current node. Equal → found. Smaller → go left. Larger → go right. Hit null → not present.

TreeNode* search(TreeNode* root, int target) {
    while (root != nullptr && root->val != target)
        root = target < root->val ? root->left : root->right;
    return root; // nullptr if not found
}

TreeNode search(TreeNode root, int target) {
    while (root != null && root.val != target)
        root = target < root.val ? root.left : root.right;
    return root; // null if not found
}

function search(root, target) {
  while (root !== null && root.val !== target)
    root = target < root.val ? root.left : root.right;
  return root; // null if not found
}

def search(root, target):
    while root is not None and root.val != target:
        root = root.left if target < root.val else root.right
    return root  # None if not found

Insert

Walk down as if searching; when you fall off the tree (reach null), that empty slot is where the new value belongs. The recursive version returns the (possibly new) subtree root, which the caller re-links:

TreeNode* insert(TreeNode* root, int val) {
    if (root == nullptr) return new TreeNode(val);
    if (val < root->val)      root->left  = insert(root->left, val);
    else if (val > root->val) root->right = insert(root->right, val);
    // equal: ignore duplicates
    return root;
}

TreeNode insert(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);
    if (val < root.val)      root.left  = insert(root.left, val);
    else if (val > root.val) root.right = insert(root.right, val);
    // equal: ignore duplicates
    return root;
}

function insert(root, val) {
  if (root === null) return new TreeNode(val);
  if (val < root.val)      root.left  = insert(root.left, val);
  else if (val > root.val) root.right = insert(root.right, val);
  // equal: ignore duplicates
  return root;
}

def insert(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    # equal: ignore duplicates
    return root

Delete — the three cases

Deletion is the tricky one because removing a node must preserve the BST property. After locating the node, handle three cases:

Leaf (no children): just remove it (return null).
One child: replace the node with that child.
Two children: replace the node’s value with its in-order successor (the smallest value in the right subtree), then delete that successor from the right subtree.

TreeNode* findMin(TreeNode* node) {
    while (node->left != nullptr) node = node->left;
    return node;
}
TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == nullptr) return nullptr;
    if (key < root->val)      root->left  = deleteNode(root->left, key);
    else if (key > root->val) root->right = deleteNode(root->right, key);
    else {
        if (root->left == nullptr)  { TreeNode* r = root->right; delete root; return r; }
        if (root->right == nullptr) { TreeNode* l = root->left;  delete root; return l; }
        TreeNode* succ = findMin(root->right);
        root->val = succ->val;
        root->right = deleteNode(root->right, succ->val);
    }
    return root;
}

TreeNode findMin(TreeNode node) {
    while (node.left != null) node = node.left;
    return node;
}
TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    if (key < root.val)      root.left  = deleteNode(root.left, key);
    else if (key > root.val) root.right = deleteNode(root.right, key);
    else {
        if (root.left == null)  return root.right;
        if (root.right == null) return root.left;
        TreeNode succ = findMin(root.right);
        root.val = succ.val;
        root.right = deleteNode(root.right, succ.val);
    }
    return root;
}

function findMin(node) {
  while (node.left !== null) node = node.left;
  return node;
}
function deleteNode(root, key) {
  if (root === null) return null;
  if (key < root.val)      root.left  = deleteNode(root.left, key);
  else if (key > root.val) root.right = deleteNode(root.right, key);
  else {
    if (root.left === null)  return root.right;
    if (root.right === null) return root.left;
    const succ = findMin(root.right);
    root.val = succ.val;
    root.right = deleteNode(root.right, succ.val);
  }
  return root;
}

def find_min(node):
    while node.left is not None:
        node = node.left
    return node

def delete_node(root, key):
    if root is None:
        return None
    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        succ = find_min(root.right)
        root.val = succ.val
        root.right = delete_node(root.right, succ.val)
    return root

For beginners: The “in-order successor” is just the next value in sorted order — the leftmost node of the right subtree. Swapping it in keeps everything ordered.

Complexity

Operation	Average	Worst (skewed)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

All use O(h) space for recursion (or O(1) for the iterative search).

Going deeper: The worst case appears with sorted input, which builds a degenerate tree. Self-balancing trees keep h = O(log n) automatically.

Next steps

Keep these operations fast with balanced trees & AVL, or measure your trees with tree height & depth.