Delete Node in a BST

Medium
1919.

Delete Node in a BST

Delete Node in a BST is a medium coding problem on binary search, trees and recursion, asked in Amazon, Microsoft and Bloomberg interviews.

You are given the root of a binary search tree with distinct values and an integer key. Remove the node holding key, if there is one, and return the root of the resulting tree, which must still be a binary search tree.

Several trees are valid after a deletion, so delete this way:

  • a node with no children is simply removed;
  • a node with one child is replaced by that child;
  • a node with two children takes the value of its in-order successor (the smallest value in its right subtree), and then that successor is deleted from the right subtree by the same rules.

If no node holds key, return the tree unchanged.

Example 1

Input
root = [5,3,6,2,4,null,7], key = 3
Output
[5,4,6,2,null,null,7]
Explanation
Node 3 has two children, so it takes the value of its in-order successor 4 (the smallest value in its right subtree), and that leaf is removed.

Example 2

Input
root = [5,3,6,2,4,null,7], key = 5
Output
[6,3,7,2,4]
Explanation
The root's successor is 6; 6 moves up into the root and its old node is replaced by its only child 7.

Example 3

Input
root = [], key = 0
Output
[]
Explanation
There is nothing to delete in an empty tree.

Constraints

  • The number of nodes in the tree is in the range [0, 10^4]
  • -10^5 <= Node.val <= 10^5
  • Each node has a unique value
  • root is a valid binary search tree
  • -10^5 <= key <= 10^5

Follow-up: Can you do it in O(height of tree) time?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function(root, key) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Delete Node in a BST — Solution in Python, Java & C++

Delete Node in a BST solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Delete Node in a BST is a medium coding problem on binary search, trees and recursion, asked in Amazon, Microsoft and Bloomberg interviews.

Problem statement

You are given the root of a binary search tree with distinct values and an integer key. Remove the node holding key, if there is one, and return the root of the resulting tree, which must still be a binary search tree.

Several trees are valid after a deletion, so delete this way:

  • a node with no children is simply removed;
  • a node with one child is replaced by that child;
  • a node with two children takes the value of its in-order successor (the smallest value in its right subtree), and then that successor is deleted from the right subtree by the same rules.

If no node holds key, return the tree unchanged.

Example 1

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Node 3 has two children, so it takes the value of its in-order successor 4 (the smallest value in its right subtree), and that leaf is removed.

Example 2

Input: root = [5,3,6,2,4,null,7], key = 5
Output: [6,3,7,2,4]
Explanation: The root's successor is 6; 6 moves up into the root and its old node is replaced by its only child 7.

Example 3

Input: root = [], key = 0
Output: []
Explanation: There is nothing to delete in an empty tree.

Constraints

  • The number of nodes in the tree is in the range [0, 10^4]
  • -10^5 <= Node.val <= 10^5
  • Each node has a unique value
  • root is a valid binary search tree
  • -10^5 <= key <= 10^5

Follow-up: Can you do it in O(height of tree) time?

Hints for Delete Node in a BST

  1. Hint 1

    First find the node: the search-tree order tells you at every step whether key is to the left or the right.

  2. Hint 2

    Removing a leaf or a node with one child is easy — its parent simply points at the child (or at nothing). The hard case is a node with two children.

  3. Hint 3

    For two children, copy the in-order successor's value into the node (the leftmost node of its right subtree) and then delete that value from the right subtree; the successor has no left child, so that second deletion is one of the easy cases.

How to solve Delete Node in a BST

Write the deletion as a recursive function that returns the new root of the subtree it was given. Searching moves left or right by comparing with key; at the node itself, the number of children decides how it is removed.

Approach

  1. If the subtree is empty, return null — the key is not there.
  2. If key < node.val, set node.left = deleteNode(node.left, key); if key > node.val, do the same on the right. Return node.
  3. Otherwise this is the node to delete. If it has no left child, return its right child; if it has no right child, return its left child.
  4. With two children, walk to the leftmost node of the right subtree, copy its value into node, then set node.right = deleteNode(node.right, thatValue).

Why it works

The in-order successor is larger than everything in the left subtree and smaller than everything else in the right subtree, so placing its value at the node keeps the search-tree order. The successor has no left child, so deleting it from the right subtree falls into the zero- or one-child case and does not cascade further.

Complexity

  • Time — O(h), where h is the height of the tree — one search path, plus one more down the right subtree
  • Space — O(h) for the recursion

Pitfalls

  • Return the subtree's new root from every call and assign it back to the parent's link — that is how a removed node actually disappears.
  • Deleting the root itself must also work: the function's return value is the new root.
  • Use the successor, as the statement fixes; using the in-order predecessor also gives a valid search tree, but a different one.

Reference solution

Python

from typing import Optional

def deleteNode(root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
    if root is None:
        return None
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        succ = root.right
        while succ.left is not None:
            succ = succ.left
        root.val = succ.val
        root.right = deleteNode(root.right, succ.val)
    return root

Java

public static 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;
}

C++

TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return nullptr;
    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) return root->right;
        if (!root->right) return root->left;
        TreeNode* succ = root->right;
        while (succ->left) succ = succ->left;
        root->val = succ->val;
        root->right = deleteNode(root->right, succ->val);
    }
    return root;
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 189 binary search problems · the whole catalogue

Learn the technique: Binary Search · Binary Trees and Tree Traversals