☕ DSA Java Articles

Topics › Binary Search Trees › Practice Problems

Delete a node in BST

Medium TUF ID 102 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the root of a binary search tree and a value key, delete the node whose value is key, if there is one, and return the root of the resulting tree. The result must still be a BST holding every other key. The root itself may be deleted, so the returned root can differ from the old one. More than one resulting shape is acceptable.

Constraints: up to 10^4 nodes; keys are distinct and fit in an int.

Example 1

          5
        /   \
       3     6          key = 3
      / \     \
     2   4     7

Two valid answers, both holding 2, 4, 5, 6, 7:

          5                      5
        /   \                  /   \
       4     6                2     6
      /       \                \     \
     2         7                4     7
   (successor copied up)    (left subtree takes its place)

Example 2

same tree, key = 0   answer = the tree unchanged

Why deletion is harder than insertion

Finding the node is an ordinary BST search. The difficulty is filling the hole. There are three cases:

Approach 1: Brute force, rebuild from the sorted keys

Intuition. Forget surgery. The inorder traversal gives every key in sorted order; remove key from that list and build a fresh balanced BST from what is left, using the middle element as the root at every level. The result is valid by construction.

Algorithm.

  1. Collect the keys in inorder (sorted) into a list.
  2. Remove key from the list if present.
  3. Build a balanced tree: the middle element is the root, the left half builds the left subtree, the right half the right subtree.
static TreeNode bruteForce(TreeNode root, int key) {
    List<Integer> keys = new ArrayList<>();
    inorder(root, keys);
    keys.remove(Integer.valueOf(key));               // remove the value, not the element at index key
    return buildBalanced(keys, 0, keys.size() - 1);
}

static void inorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    inorder(node.left, out);
    out.add(node.val);
    inorder(node.right, out);
}

static TreeNode buildBalanced(List<Integer> keys, int lo, int hi) {
    if (lo > hi) return null;
    int mid = (lo + hi) >>> 1;
    TreeNode node = new TreeNode(keys.get(mid));
    node.left = buildBalanced(keys, lo, mid - 1);
    node.right = buildBalanced(keys, mid + 1, hi);
    return node;
}

Complexity. Time O(n): one traversal, one removal and one rebuild. Space O(n) for the list and the new nodes.

The Integer.valueOf(key) is essential. List<Integer> has two remove methods: remove(int index) and remove(Object o). Passing a plain int picks the index version, which would delete the element at position key, or throw when key is out of range.

Approach 2: Recursive, copy the inorder successor up

Intuition. For a node x with two children, find a key that could sit at x’s position: it must be larger than everything in L and smaller than everything else in R. The inorder successor, the smallest key in R, fits exactly. It is larger than x, hence larger than all of L, and by definition smaller than every other key in R. So copy the successor’s value into x, then delete the successor from R. That second deletion is always an easy case: the successor is the leftmost node of R, so it has no left child.

Algorithm.

  1. If the subtree is empty, return null (the key was not found).
  2. If key < root.val, delete from the left subtree and reattach it; if key > root.val, do the same on the right.
  3. Otherwise this is the node. If it has no left child, return its right child; if it has no right child, return its left child. This covers the leaf and one-child cases.
  4. With two children: walk to the leftmost node of the right subtree, copy its value into root, then delete that value from the right subtree.
  5. Return root.
static TreeNode successorDelete(TreeNode root, int key) {
    if (root == null) return null;                   // key not found
    if (key < root.val) {
        root.left = successorDelete(root.left, key);
    } else if (key > root.val) {
        root.right = successorDelete(root.right, key);
    } else {
        if (root.left == null) return root.right;    // zero or one child: splice the node out
        if (root.right == null) return root.left;
        TreeNode succ = root.right;
        while (succ.left != null) succ = succ.left;  // smallest key in the right subtree
        root.val = succ.val;                         // copy it up ...
        root.right = successorDelete(root.right, succ.val); // ... and delete it below (it has no left child)
    }
    return root;
}

Complexity. Time O(h): one walk down to the node, one walk down to the successor, and the second recursive delete follows that same path. Space O(h) for the recursion. The height never increases, which is the main advantage of this method.

Copying the value rather than moving nodes is fine for this problem. If other code held references to specific nodes, you would relink the successor node into x’s position instead.

Approach 3: Optimal, iterative with a subtree join

Intuition. Merge L and R directly. Let m be the largest key in L, its rightmost node. Every key in R is larger than every key in L, including m, and m has no right child. So hang R as the right subtree of m, and let L take x’s place.

Why is this still a BST? On the way from L’s root down to m we went right at every step, so R lands in the right subtree of each of those nodes, and all of its keys are indeed larger. For x’s old parent, the whole replacement subtree consists of keys that were already on the correct side of it. If L is empty, the replacement is simply R, and vice versa.

The search for the parent is done with a loop that inspects the child before stepping into it, so we always hold the link that has to change. A deleted root is handled separately, because it has no parent.

Algorithm.

  1. If the tree is empty, return null. If the root holds key, return joinChildren(root).
  2. Walk from the root. At each node, look at the child on key’s side. If that child holds key, replace the link with joinChildren(child) and stop; otherwise move to it. Falling off the tree means the key is absent.
  3. joinChildren(node): if a side is empty, return the other side. Otherwise find the rightmost node of node.left, set its right link to node.right, and return node.left.
static TreeNode optimal(TreeNode root, int key) {
    if (root == null) return null;
    if (root.val == key) return joinChildren(root);
    TreeNode cur = root;
    while (cur != null) {
        if (key < cur.val) {
            if (cur.left != null && cur.left.val == key) { cur.left = joinChildren(cur.left); break; }
            cur = cur.left;
        } else {
            if (cur.right != null && cur.right.val == key) { cur.right = joinChildren(cur.right); break; }
            cur = cur.right;
        }
    }
    return root;
}

/** The subtree that replaces a deleted node. */
static TreeNode joinChildren(TreeNode node) {
    if (node.left == null) return node.right;
    if (node.right == null) return node.left;
    TreeNode rightmost = node.left;
    while (rightmost.right != null) rightmost = rightmost.right; // largest key of the left subtree
    rightmost.right = node.right;                    // every key on the right is larger than it
    return node.left;
}

Dry run on Example 1 (key = 3):

step node observation action
1 5 root is not 3; 3 < 5, left child is 3 call joinChildren(3)
2 3 has left 2 and right 4 rightmost of left subtree is 2
3 2 2.right is empty set 2.right = 4, return 2
4 5   5.left = 2; result [5, 2, 6, null, 4, null, 7]

Complexity. Time O(h): one walk to the node and one walk down the right edge of L. Space O(1).

The trade-off is height. Hanging R below the deepest right node of L can make the tree taller: deleting the root 5 from Example 1 gives 3 as the new root, with 6 → 7 hanging under 4, height 4 instead of 3. Approach 2 never does this, so it is the better choice when the tree is reused for many operations, while Approach 3 wins on stack space.

Edge cases and pitfalls