Binary Search Tree

Deletion

What is BST Deletion?

Deleting from a Binary Search Tree starts the same way insertion does — you search for the value by comparing and moving left or right — but once you find it, keeping the tree a valid BST afterward takes more care than insertion ever did, because removing a node can leave a gap that needs to be patched correctly.

How Does It Work?

There are exactly three shapes the node-to-delete can have, and each is handled differently: a leaf is simply removed, a node with one child is replaced by that child, and a node with two children is trickier — you can't just delete it without breaking the ordering, so you borrow a replacement value from elsewhere in the tree.

Case 1: Deleting a leaf
No children to worry about — just remove the node outright. The parent's pointer to it becomes null.
Case 2: Deleting a node with one child
Splice the node out by connecting its parent directly to its single child, skipping over the deleted node entirely.
Case 3: Deleting a node with two children
Find the in-order successor (the smallest value in the right subtree), copy that value into the node being deleted, then delete the successor from its original spot — which is guaranteed to be a leaf or have only a right child, so it reduces to Case 1 or Case 2.
Deleting 8 (two children)
83121014
10 (successor) takes its place
1031214
Node being deletedIn-order successorSuccessor's new position

Algorithm Steps

  1. Search for the value the same way you would for lookup
  2. Once found, check how many children the node has:
    • Zero children → remove it directly
    • One child → replace the node with that child
    • Two children → find the in-order successor, copy its value up, then delete the successor
  3. Return the (possibly modified) subtree to the parent call

Time Complexity

  • Best/Average Case: Roughly balanced tree → O(log n).
  • Worst Case: Degenerate/skewed tree → O(n).

Time Complexity Analysis

Advertisement

Space Complexity

Deletion needs O(1) extra space beyond the recursion stack — no matter which of the three cases applies, only a constant number of pointers get rewired.

Repeated deletions (and insertions) can gradually unbalance a BST even if it started out balanced, which is exactly the problem self-balancing trees like AVL and Red-Black trees are designed to prevent — they perform extra rotation work on every insert/delete specifically to keep the height close to log n.

Daily DSA Challenge by Scale Engineer

Delete a value and watch how its replacement (if any) is chosen

Tree is empty
No tree yet — insert a value or generate a random tree
Internal nodeLeaf nodeRootSearch pathBeing deletedIn-order successor

Test Your Knowledge before moving forward!

BST Deletion Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Binary Search Tree Deletion Implementation

// Binary Search Tree node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Delete a value from the BST
function deleteNode(node, value) {
  if (node === null) return null;

  if (value < node.value) {
    node.left = deleteNode(node.left, value);
    return node;
  }
  if (value > node.value) {
    node.right = deleteNode(node.right, value);
    return node;
  }

  // Found the node to delete
  if (node.left === null && node.right === null) return null; // Case 1: leaf
  if (node.left === null) return node.right;                  // Case 2: only right child
  if (node.right === null) return node.left;                  // Case 2: only left child

  // Case 3: two children — find in-order successor (min of right subtree)
  let successor = node.right;
  while (successor.left !== null) successor = successor.left;

  node.value = successor.value;
  node.right = deleteNode(node.right, successor.value);
  return node;
}

// Usage example
let root = null;
[8, 3, 12, 10, 14].forEach((value) => {
  root = insertNode(root, value); // see BST Insertion for insertNode
});
root = deleteNode(root, 8);

Done With the Learning

Mark BST Deletion as done and view it on your dashboard

Explore Other Tree Topics

BST Insertion

BST Searching

AVL Balancing

Binary Tree Types

Structure & Properties