Command Palette

Search for a command to run...

Hectal
Problem 17.8 · Binary Search TreesMedium

Delete Node in a BST

PatternBST Ordering

What it teaches: The three deletion cases, with the in-order successor for nodes that have two children.

Practise it on judges as “Delete Node in a BST”.

The problem

Delete the node with value key (if present) and return the root. When the node has two children, replace its value with its in-order successor (the smallest value in its right subtree) and delete that successor.

Example 1

Input: root = [5, 3, 6, 2, 4, null, 7], key = 3
Output: [5, 4, 6, 2, null, null, 7]

Constraints

  • 0 ≤ nodes ≤ 10⁴
  • Distinct values

Pattern clues in the wording

  • → Remove from a BST and keep it valid

These clues point to BST Ordering: Use left < node < right to skip half the tree, and in-order traversal to visit values in sorted order.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        return root;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
root = [5,3,6,2,4,null,7]
key = 3
[5,4,6,2,null,null,7]
2
root = [5,3,6,2,4,null,7]
key = 0
[5,3,6,2,4,null,7]
3
root = [5,3,6,2,4,null,7]
key = 5
[6,3,7,2,4]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Recursive delete · O(h)
1

Recursive delete

Time O(h) Space O(h)

Recurse left or right to find key. At the node: return the non-null child if one is missing; otherwise copy the successor and delete it on the right.

Approach 1
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 s = root.right;
            while (s.left != null) s = s.left;
            root.val = s.val;
            root.right = deleteNode(root.right, s.val);
        }
        return root;
    }
}

Verdict: Standard textbook delete.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Key missing
  • Deleting the root
  • Deleting a leaf

Mistakes people make

  • Losing a subtree by returning null when the node has one child.

Interview

Follow-up questions

Why the successor and not any value?