Binary Search Tree Deletion

Learn Binary Search Tree Deletion with practical examples, explanations, best practices, and real-world coding techniques.

What Is Binary Search Tree Deletion?

Binary Search Tree deletion is the process of removing a node from a Binary Search Tree while preserving the tree's ordering property. Unlike insertion and search, deletion requires different handling depending on how many children the target node has.

There are three fundamental deletion cases:

  • The node is a leaf and has no children.
  • The node has exactly one child.
  • The node has two children.

Correctly handling these cases allows the remaining nodes to continue satisfying the Binary Search Tree ordering rule.

BST Deletion Rule

After deleting a node, the resulting tree must still satisfy the BST property: smaller values remain in the left subtree and greater values remain in the right subtree.

Consider this tree: 

        50
       /  \
     30    70
    /  \  /  \
  20   40 60   80

Removing 20 is simple because it has no children. Removing 30 is more involved because it has two children. Removing 70 also requires selecting a replacement value while preserving the ordering of the tree.

Case 1: Deleting a Leaf Node

A leaf node has no left or right child. Because it does not have any descendants that need to be connected elsewhere, it can simply be removed.

Consider deleting 20: 

Before:

        50
       /  \
     30    70
    /
  20

After deleting 20:

        50
       /  \
     30    70

The parent node's reference to 20 becomes null.

Case 2: Deleting a Node with One Child

If the target node has exactly one child, the child can replace the deleted node. This connects the child directly to the deleted node's parent.

For example: 

Before:

    50
   /
  30
    \
     40

If 30 is deleted, its only child, 40, takes its position: 

After:

    50
   /
  40

The subtree remains a valid BST because 40 is still smaller than 50.

Case 3: Deleting a Node with Two Children

The two-child case is the most important part of BST deletion. Simply removing the node would disconnect two subtrees, so a replacement value must be selected.

A common solution is to replace the target with its inorder successor. The inorder successor is the smallest value in the target's right subtree.

Another valid approach is to use the inorder predecessor, which is the largest value in the target's left subtree.

Using the Inorder Successor

Consider deleting 50 from this tree: 

        50
       /  \
     30    70
          /  \
        60    80

The right subtree of 50 begins at 70. The smallest value in that subtree is 60, so 60 is the inorder successor of 50.

Replace 50 with 60: 

        60
       /  \
     30    70
            \
             80

The original 60 node is then removed from its previous location. The resulting structure remains a valid BST.

Finding the Inorder Successor

To find the inorder successor when a node has a right subtree, move to the right child and then continue moving left until there is no more left child. 

function findMin(root) {
  let current = root;

  while (current.left !== null) {
    current = current.left;
  }

  return current;
}

The leftmost node in the right subtree contains the smallest value that is greater than the deleted node.

Finding the Inorder Predecessor

Instead of using the inorder successor, deletion can use the inorder predecessor. The predecessor is the largest value in the target node's left subtree. 

function findMax(root) {
  let current = root;

  while (current.right !== null) {
    current = current.right;
  }

  return current;
}

Both replacement strategies preserve the BST ordering property when implemented correctly.

Recursive BST Deletion

A recursive implementation first searches for the target node. Once the node is found, the appropriate deletion case is applied. 

function deleteNode(root, value) {
  if (root === null) {
    return null;
  }

  if (value < root.value) {
    root.left = deleteNode(root.left, value);
  } else if (value > root.value) {
    root.right = deleteNode(root.right, value);
  } else {
    // Case 1: no left child
    if (root.left === null) {
      return root.right;
    }

    // Case 2: no right child
    if (root.right === null) {
      return root.left;
    }

    // Case 3: two children
    const successor = findMin(root.right);

    root.value = successor.value;
    root.right = deleteNode(root.right, successor.value);
  }

  return root;
}

The two one-child checks also handle the leaf case. If both children are null, the function returns null and removes the node from its parent.

Complete BST Deletion Example

The following example builds a BST and deletes values using the same deletion function. 

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function insert(root, value) {
  if (root === null) {
    return new Node(value);
  }

  if (value < root.value) {
    root.left = insert(root.left, value);
  } else if (value > root.value) {
    root.right = insert(root.right, value);
  }

  return root;
}

function findMin(root) {
  let current = root;

  while (current.left !== null) {
    current = current.left;
  }

  return current;
}

function deleteNode(root, value) {
  if (root === null) {
    return null;
  }

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

    if (root.right === null) {
      return root.left;
    }

    const successor = findMin(root.right);

    root.value = successor.value;
    root.right = deleteNode(root.right, successor.value);
  }

  return root;
}

let root = null;

[50, 30, 70, 20, 40, 60, 80].forEach(value => {
  root = insert(root, value);
});

root = deleteNode(root, 20);
root = deleteNode(root, 30);
root = deleteNode(root, 50);

Why the Two-Child Case Works

The inorder successor is chosen because it is the smallest value greater than the target. Replacing the target with this value preserves the ordering relationship with both sides of the tree.

After copying the successor's value into the target node, the successor itself must still be deleted. The important observation is that the successor cannot have a left child, because it was selected as the leftmost node in the right subtree.

Deletion from the Root

The root can be deleted using exactly the same three cases. The only difference is that the returned subtree becomes the new root. 

let root = new Node(50);

root.left = new Node(30);
root.right = new Node(70);

root = deleteNode(root, 50);

console.log(root.value);

Reassigning the result to root is important because the original root may be replaced by one of its children or by a subtree containing the inorder successor.

Deletion Step by Step

Consider this BST and remove 70: 

        50
       /  \
     30    70
          /  \
        60    80
             /
            75
  1. Start at 50.
  2. 70 is greater than 50, so move right.
  3. Find the target node 70.
  4. The target has two children, 60 and 80.
  5. Find the smallest value in the right subtree.
  6. The successor is 75.
  7. Replace 70 with 75.
  8. Delete the original 75 node from the right subtree.

The resulting tree is: 

        50
       /  \
     30    75
          /  \
        60    80

Deletion When the Value Does Not Exist

If the target value does not exist, the search eventually reaches a null subtree. The tree remains unchanged. 

root = deleteNode(root, 999);

No replacement or structural modification is required because there is no matching node.

Deletion Complexity

BST deletion takes O(h) time, where h is the height of the tree. Finding the target and, when necessary, finding its inorder successor both follow paths whose lengths are bounded by the tree height.

Tree Shape Deletion Time
Balanced BST O(log n)
Average case O(log n)
Skewed BST O(n)

Recursive deletion uses O(h) auxiliary space because of the call stack. An iterative implementation can reduce the auxiliary traversal space to O(1).

Inorder Traversal After Deletion

Inorder traversal is useful for verifying that deletion has preserved the BST ordering property. 

function inorder(root, result = []) {
  if (root === null) {
    return result;
  }

  inorder(root.left, result);
  result.push(root.value);
  inorder(root.right, result);

  return result;
}

let root = null;

[50, 30, 70, 20, 40, 60, 80].forEach(value => {
  root = insert(root, value);
});

console.log(inorder(root));
// [20, 30, 40, 50, 60, 70, 80]

root = deleteNode(root, 30);

console.log(inorder(root));
// [20, 40, 50, 60, 70, 80]

Successor vs Predecessor

Both the inorder successor and inorder predecessor can be used when deleting a node with two children. The choice does not change the fundamental BST property as long as the replacement is selected correctly and the original replacement node is removed.

Replacement Location Value
Inorder successor Right subtree Smallest value greater than target
Inorder predecessor Left subtree Largest value smaller than target

Deletion and Tree Balance

A normal Binary Search Tree does not automatically rebalance itself after deletion. Removing a node can change the shape of the tree, but no rotations are performed by the standard BST deletion algorithm.

If guaranteed logarithmic height is required after repeated insertions and deletions, self-balancing structures such as AVL Trees or Red-Black Trees are more appropriate.

Common BST Deletion Mistakes

  • Removing a node with two children without reconnecting its subtrees.
  • Choosing an arbitrary replacement value for a two-child node.
  • Finding the successor without removing its original node afterward.
  • Forgetting to return the replacement subtree from the recursive function.
  • Failing to update root when the deleted node is the root.
  • Confusing the inorder successor with the largest value in the right subtree.
  • Assuming deletion automatically balances a normal BST.
  • Not handling deletion when the target value is absent.

BST Deletion Case Summary

Node Type Action
Leaf Remove the node and return null
One child Replace the node with its child
Two children Replace with inorder successor or predecessor, then remove the replacement node

Key Takeaways

  • BST deletion must preserve the tree's ordering property.
  • A leaf node can be removed directly.
  • A node with one child can be replaced by that child.
  • A node with two children can use its inorder successor or predecessor as a replacement.
  • The inorder successor is the smallest value in the right subtree.
  • The inorder predecessor is the largest value in the left subtree.
  • Deletion takes O(h), where h is the tree height.
  • A balanced BST provides O(log n) deletion.
  • A skewed BST can require O(n) deletion.
  • A normal BST does not automatically rebalance after deletion.

Code Examples 

function findMin(root) {
  if (root === null) {
    return null;
  }

  let current = root;

  while (current.left !== null) {
    current = current.left;
  }

  return current;
}
    
function deleteNode(root, value) {
  if (root === null) {
    return null;
  }

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

    if (root.right === null) {
      return root.left;
    }

    const successor = findMin(root.right);

    root.value = successor.value;
    root.right = deleteNode(root.right, successor.value);
  }

  return root;
}
    
function inorder(root, result = []) {
  if (root === null) {
    return result;
  }

  inorder(root.left, result);
  result.push(root.value);
  inorder(root.right, result);

  return result;
}

let root = null;

[50, 30, 70, 20, 40, 60, 80].forEach(value => {
  root = insert(root, value);
});

console.log("Before:", inorder(root));

root = deleteNode(root, 30);

console.log("After:", inorder(root));

Pro Tip

For the two-child deletion case, remember the simplest rule: replace the node with the smallest value from its right subtree, then delete that replacement node. The replacement is guaranteed to have no left child, which reduces the second deletion to an easier case.

🎨 IgKnight Docs

Master HTML, CSS, JS, Python, .NET and more with easy-to-follow lessons and practical code examples.

© 2025 IgKnight Learning Platform. All rights reserved.