Delete Node in a BST

Medium Trees & BST BST Basics Original on LeetCode

Delete Node in a BST is a medium trees & bst problem solved with the bst basics pattern. The best approach, optimal (recursive delete with in-order successor), runs in O(h) time and O(h) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (rebuild from in-order) up.

Problem

You are given the root of a binary search tree and an integer key. Remove the node whose value is key, if there is one, and return the root of the resulting tree (which may be a different node than before).

The tree you return must still be a valid binary search tree holding all the other values. When the deleted node has two children there is more than one correct shape; any valid result is accepted.

Examples

Example 1

Input
root = [8, 3, 12, 1, 6, null, 15], key = 3
Output
[8, 6, 12, 1, null, null, 15]
Why
Node 3 has two children. Its in-order successor 6 takes its place. [8, 1, 12, null, 6, null, 15] is also accepted.

Example 2

Input
root = [8, 3, 12, 1, 6, null, 15], key = 10
Output
[8, 3, 12, 1, 6, null, 15]
Why
10 is not in the tree, so nothing changes.

Example 3

Input
root = [], key = 4
Output
[]
Why
Deleting from an empty tree leaves it empty.

Constraints

  • The tree has 0 to 10^4 nodes.
  • -10^5 <= Node.val, key <= 10^5
  • All node values are distinct, and root is a valid binary search tree.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (rebuild from in-order)O(n)O(n)
Optimal (recursive delete with in-order successor)O(h)O(h)

1Brute force (rebuild from in-order)

TimeO(n)Every node is visited once by the traversal and created once by the rebuild, even though only one node had to go.
SpaceO(n)The list of values plus a whole new tree.

An in-order walk of a BST lists its values in sorted order. Collect every value except the key, then build a fresh balanced BST from that sorted list.

  1. Do an in-order traversal and append every value that is not equal to key.
  2. Build a BST from the sorted list: the middle element becomes the root, the left half the left subtree, the right half the right subtree.
  3. Return the new root (null if the list is empty).
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        List<Integer> vals = new ArrayList<>();
        collect(root, key, vals);
        return build(vals, 0, vals.size() - 1);
    }

    private void collect(TreeNode node, int key, List<Integer> vals) {
        if (node == null) return;
        collect(node.left, key, vals);
        if (node.val != key) vals.add(node.val);
        collect(node.right, key, vals);
    }

    private TreeNode build(List<Integer> vals, int lo, int hi) {
        if (lo > hi) return null;
        int mid = (lo + hi) / 2;
        TreeNode node = new TreeNode(vals.get(mid));
        node.left = build(vals, lo, mid - 1);
        node.right = build(vals, mid + 1, hi);
        return node;
    }
}

2Optimal (recursive delete with in-order successor)

TimeO(h)One path down to the node plus one path down to its successor, where h is the tree height (log n when balanced, n when skewed).
SpaceO(h)The recursion stack is at most the height of the tree.

Walk down using the BST order. When you reach the node: if it has at most one child, return that child to its parent. If it has two children, copy the smallest value of its right subtree into it and then delete that value from the right subtree, which removes a node with at most one child.

  1. If root is null, return null.
  2. If key < root.val, set root.left = deleteNode(root.left, key); if key > root.val, do the same on the right.
  3. Otherwise this is the node: if it has no left child return root.right; if it has no right child return root.left.
  4. Two children: find the leftmost node of root.right, copy its value into root, then root.right = deleteNode(root.right, that value).
  5. Return root.
class Solution {
    public 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 = root.right;
            while (succ.left != null) succ = succ.left;
            root.val = succ.val;
            root.right = deleteNode(root.right, succ.val);
        }
        return root;
    }
}

Edge cases to test

  • The key is not in the tree
  • Deleting the root, including a root with a single node
  • Deleting a leaf, a node with only a left child, a node with only a right child
  • Deleting a node with two children whose successor has a right subtree

Hints

Hint 1

Use the BST order to walk to the node: go left when key is smaller, right when it is larger.

Hint 2

A node with zero or one child is easy: replace it with that child (or with null).

Hint 3

For two children, copy in the smallest value of the right subtree (the in-order successor), then delete that value from the right subtree.

FAQ

What is the best time complexity for Delete Node in a BST?

Optimal (recursive delete with in-order successor) runs in O(h) time and O(h) extra space. One path down to the node plus one path down to its successor, where h is the tree height (log n when balanced, n when skewed).

Which pattern does Delete Node in a BST use?

It is a trees & bst problem that uses the bst basics pattern. Other problems with the same pattern: Search in a Binary Search Tree, Minimum element in BST, Insert into a Binary Search Tree.

Is there a brute force solution for Delete Node in a BST?

Yes. Brute force (rebuild from in-order) takes O(n) time and O(n) space. An in-order walk of a BST lists its values in sorted order.

Which edge cases should I test for Delete Node in a BST?

The key is not in the tree; Deleting the root, including a root with a single node; Deleting a leaf, a node with only a left child, a node with only a right child; Deleting a node with two children whose successor has a right subtree.