Scale Engineer

Delete Node in a BST

Med
#0437Time: O(H), where H is the height of the tree. In a balanced BST, H is approximately log(N), leading to O(log N) time. In the worst case of a skewed tree, H is N, leading to O(N) time.Space: O(H) for the recursion call stack, where H is the height of the tree. In the worst case of a skewed tree, this can be O(N).
Data structures
TreeBinary TreeBinary Search Tree

Prompt

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

  1. Search for a node to remove.
  2. If the node is found, delete the node.

 

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.

Example 3:

Input: root = [], key = 0
Output: []

 

Constraints:

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

 

Follow up: Could you solve it with time complexity O(height of tree)?

Approaches

2 approaches with complexity analysis and trade-offs.

This approach utilizes recursion to traverse the Binary Search Tree. The function calls itself on the left or right subtree based on the comparison between the node's value and the key. Once the target node is found, it's deleted according to one of three cases: the node has no children, one child, or two children. The recursive structure elegantly handles the re-linking of nodes after deletion.

Algorithm

  • If root is null, return null.
  • If key < root.val, recursively call delete on the left subtree: root.left = deleteNode(root.left, key).
  • If key > root.val, recursively call delete on the right subtree: root.right = deleteNode(root.right, key).
  • If key == root.val, the node is found. Handle the three deletion cases:
    • Case 1 (0 or 1 child): If root.left is null, return root.right. If root.right is null, return root.left.
    • Case 2 (2 children): Find the in-order successor (minimum node in the right subtree). Copy its value to the current node. Recursively delete the successor node from the right subtree.
  • Return the root.

Walkthrough

The core of this method is a function deleteNode(root, key) that returns the root of the modified subtree.

  • Base Case: If the root is null, it means the key is not present in the tree, so we return null.

  • Search Phase:

    • If the key is less than root.val, the node to be deleted lies in the left subtree. We make a recursive call: root.left = deleteNode(root.left, key).
    • If the key is greater than root.val, it must be in the right subtree. We recurse on the right: root.right = deleteNode(root.right, key).

  • Deletion Phase (key == root.val):

    1. Node with 0 or 1 child: If root.left is null, we can simply replace the current node with its right child (root.right). Similarly, if root.right is null, we replace it with root.left. This single check handles both the leaf node case (where both children are null) and the single-child case.
    2. Node with 2 children: This is the complex case. To maintain the BST property, we must replace the node's value with its in-order successor (the smallest value in its right subtree).
      • Find the minimum node in the right subtree.
      • Copy the successor's value to the current node (root.val = successor.val).
      • Now, we must delete that successor node from the right subtree. We do this by making another recursive call: root.right = deleteNode(root.right, root.val). Since the successor is the minimum element, it has at most one (right) child, so its deletion will fall into the simpler case (1).

The assignments root.left = ... and root.right = ... are crucial as they update the tree structure by connecting the parent node to the new root of the modified subtree.

class Solution {    /**     * Finds the node with the minimum value in a given subtree.     */    private TreeNode findMin(TreeNode node) {        while (node.left != null) {            node = node.left;        }        return node;    }     public TreeNode deleteNode(TreeNode root, int key) {        // Base case: if the tree is empty, return null.        if (root == null) {            return null;        }         // Recurse down the tree        if (key < root.val) {            root.left = deleteNode(root.left, key);        } else if (key > root.val) {            root.right = deleteNode(root.right, key);        } else {            // Node to be deleted is found                        // Case 1 & 2: Node with one or no child            if (root.left == null) {                return root.right;            } else if (root.right == null) {                return root.left;            }             // Case 3: Node with two children            // Find the in-order successor (smallest in the right subtree)            TreeNode successor = findMin(root.right);            // Copy the successor's content to this node            root.val = successor.val;            // Delete the in-order successor from the right subtree            root.right = deleteNode(root.right, root.val);        }        return root;    }}

Complexity

Time

O(H), where H is the height of the tree. In a balanced BST, H is approximately log(N), leading to O(log N) time. In the worst case of a skewed tree, H is N, leading to O(N) time.

Space

O(H) for the recursion call stack, where H is the height of the tree. In the worst case of a skewed tree, this can be O(N).

Trade-offs

Pros

  • The code is clean, concise, and closely follows the recursive definition of a tree, making it easier to reason about.

  • Handles all deletion cases elegantly within a single function.

Cons

  • The recursive calls consume stack space, which can lead to a StackOverflowError for very deep trees (e.g., a skewed tree with many nodes).

  • Slightly higher overhead than an iterative solution due to function call mechanics.

Solutions

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode deleteNode ( TreeNode root , int key ) { if ( root == null ) { return null ; } if ( root . val > key ) { root . left = deleteNode ( root . left , key ); return root ; } if ( root . val < key ) { root . right = deleteNode ( root . right , key ); return root ; } if ( root . left == null ) { return root . right ; } if ( root . right == null ) { return root . left ; } TreeNode node = root . right ; while ( node . left != null ) { node = node . left ; } node . left = root . left ; root = root . right ; return root ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem