Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Delete Node in a BST

MEDIUMProblemSolveExternal Links

Description

Given the root of a Binary Search Tree (BST) and an integer key, delete the node with the value equal to key from the BST. Return the root node reference of the resulting BST (which may have changed).

The deletion process can be broken into two stages:

  1. Search for the node whose value matches the given key.
  2. Delete the node if it is found, while preserving the BST property.

Recall that a BST satisfies the rule: for every node, all values in its left subtree are strictly smaller, and all values in its right subtree are strictly larger. After deletion, this property must still hold for every remaining node.

Binary Search Tree with nodes 5, 3, 6, 2, 4, 7 showing the node to delete (3) and the three deletion cases
Binary Search Tree with nodes 5, 3, 6, 2, 4, 7 showing the node to delete (3) and the three deletion cases

Examples

Example 1

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

Output: [5, 4, 6, 2, null, null, 7]

Explanation: We need to delete the node with value 3. Node 3 has two children: left child 2 and right child 4. To maintain the BST property, we find the inorder successor of node 3, which is node 4 (the smallest value in the right subtree of 3). We replace node 3's value with 4, then delete the original node 4 (which is a leaf). The resulting tree has root 5, with left child 4 (having left child 2), and right child 6 (having right child 7). Another valid answer is [5, 2, 6, null, 4, null, 7] where we use the inorder predecessor instead.

Example 2

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

Output: [5, 3, 6, 2, 4, null, 7]

Explanation: The key 0 does not exist in the BST. Since no node has the value 0, the tree remains unchanged. We simply return the original root.

Example 3

Input: root = [], key = 0

Output: []

Explanation: The tree is empty, so there is nothing to delete. We return null (empty tree).

Constraints

  • 0 ≤ Number of nodes ≤ 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

Editorial

Brute Force

Intuition

The most straightforward way to think about deleting from a BST is to not worry about restructuring the tree in-place at all. Instead, we can:

  1. Perform an inorder traversal of the BST to collect all node values in sorted order.
  2. Remove the key from this sorted list.
  3. Rebuild a balanced BST from the remaining sorted values.

Think of it like a bookshelf sorted alphabetically. If you need to remove one book, you could take every book off the shelf, remove the unwanted one, and then put them all back in order. This works correctly but involves a lot of unnecessary lifting.

This approach ignores the structure of the BST entirely and just uses the fact that an inorder traversal of a BST gives sorted output. It is wasteful because we tear down and rebuild the entire tree just to remove one node.

Step-by-Step Explanation

Let's trace through with root = [5, 3, 6, 2, 4, null, 7], key = 3:

Step 1: Perform inorder traversal of the BST.

  • Visit: 2 → 3 → 4 → 5 → 6 → 7
  • Sorted list: [2, 3, 4, 5, 6, 7]

Step 2: Remove key = 3 from the sorted list.

  • List after removal: [2, 4, 5, 6, 7]

Step 3: Build a balanced BST from [2, 4, 5, 6, 7].

  • Pick middle element 5 as root.
  • Left half [2, 4]: pick 4 as left child of 5, with 2 as left child of 4.
  • Right half [6, 7]: pick 6 as right child of 5, with 7 as right child of 6.

Step 4: Return the new root (5).

  • Result tree: [5, 4, 6, 2, null, null, 7]

This gives a valid BST with node 3 removed.

Brute Force — Flatten, Remove, Rebuild — Watch how we collect all BST values via inorder traversal, remove the target key, and rebuild the tree from the remaining sorted values.

Algorithm

  1. Perform an inorder traversal of the BST to collect all node values into a sorted array.
  2. Remove the key from the sorted array (if present).
  3. Build a balanced BST from the remaining sorted array:
    • Pick the middle element as the root.
    • Recursively build the left subtree from the left half.
    • Recursively build the right subtree from the right half.
  4. Return the root of the newly built BST.

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void inorder(TreeNode* root, vector<int>& vals) {
        if (!root) return;
        inorder(root->left, vals);
        vals.push_back(root->val);
        inorder(root->right, vals);
    }
    
    TreeNode* buildBST(vector<int>& vals, int left, int right) {
        if (left > right) return nullptr;
        int mid = left + (right - left) / 2;
        TreeNode* node = new TreeNode(vals[mid]);
        node->left = buildBST(vals, left, mid - 1);
        node->right = buildBST(vals, mid + 1, right);
        return node;
    }
    
    TreeNode* deleteNode(TreeNode* root, int key) {
        vector<int> vals;
        inorder(root, vals);
        
        // Remove key from sorted list
        auto it = find(vals.begin(), vals.end(), key);
        if (it != vals.end()) {
            vals.erase(it);
        }
        
        return buildBST(vals, 0, vals.size() - 1);
    }
};
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        # Step 1: Inorder traversal to collect sorted values
        vals = []
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            vals.append(node.val)
            inorder(node.right)
        
        inorder(root)
        
        # Step 2: Remove the key
        if key in vals:
            vals.remove(key)
        
        # Step 3: Build balanced BST from sorted array
        def build_bst(left, right):
            if left > right:
                return None
            mid = (left + right) // 2
            node = TreeNode(vals[mid])
            node.left = build_bst(left, mid - 1)
            node.right = build_bst(mid + 1, right)
            return node
        
        return build_bst(0, len(vals) - 1)
/**
 * 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 {
    private List<Integer> vals = new ArrayList<>();
    
    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        vals.add(root.val);
        inorder(root.right);
    }
    
    private TreeNode buildBST(int left, int right) {
        if (left > right) return null;
        int mid = left + (right - left) / 2;
        TreeNode node = new TreeNode(vals.get(mid));
        node.left = buildBST(left, mid - 1);
        node.right = buildBST(mid + 1, right);
        return node;
    }
    
    public TreeNode deleteNode(TreeNode root, int key) {
        inorder(root);
        vals.remove(Integer.valueOf(key));
        return buildBST(0, vals.size() - 1);
    }
}

Complexity Analysis

Time Complexity: O(n)

The inorder traversal visits all n nodes, taking O(n). Removing the key from the list takes O(n) in the worst case (shifting elements). Rebuilding the BST from the sorted array takes O(n) since we visit each value once. Overall: O(n).

Space Complexity: O(n)

We store all n values in an array. The recursive call stack for building the BST goes O(log n) deep (since we always pick the middle). The dominant space cost is the array itself: O(n).

Why This Approach Is Not Efficient

The brute force approach always does O(n) work regardless of where the target node is in the tree. Even if the node to delete is the root or a leaf, we still traverse the entire tree, build a full sorted array, remove the element, and rebuild the entire tree from scratch.

This is wasteful because BST structure gives us a powerful property: we can locate any node in O(h) time (where h is the height of the tree) by following left/right comparisons. A well-structured deletion should only modify the local neighborhood of the deleted node, leaving the rest of the tree untouched.

For a balanced BST with 10,000 nodes, the brute force does ~10,000 operations, while an in-place approach would do only ~14 operations (log₂(10,000) ≈ 13.3). We are doing ~700× more work than necessary.

The key insight: instead of tearing down and rebuilding the entire tree, we can search for the node using BST properties, then handle deletion by restructuring only the affected subtree.

Optimal Approach - Recursive BST Deletion

Intuition

Instead of flattening and rebuilding, we take advantage of the BST structure to locate the target node efficiently and handle its deletion in-place.

Think of a BST like a sorted filing cabinet where each drawer tells you whether to look left (smaller) or right (larger). To remove a file, you walk directly to the right drawer — you do not dump all files on the floor and re-file them.

Once we locate the node to delete, there are three cases:

Case 1 — Leaf node (no children): Simply remove the node. Nothing else to adjust since it has no descendants.

Case 2 — One child: The node acts as a bridge between its parent and its single child. Removing it is like removing a middle link in a chain — we just connect the parent directly to the child.

Case 3 — Two children: This is the trickiest case. We cannot simply remove the node because both subtrees need a parent. The solution is to find the node's inorder successor — the smallest value in the right subtree. This value is guaranteed to be larger than everything in the left subtree and smaller than everything else in the right subtree. We replace the target node's value with the successor's value, then recursively delete the successor from the right subtree (which reduces to Case 1 or Case 2, since the inorder successor has at most one child).

This recursive approach naturally handles all cases and modifies only the nodes along the search path.

Step-by-Step Explanation

Let's trace through with root = [5, 3, 6, 2, 4, null, 7], key = 3:

Step 1: Start at root (5). Compare key=3 with root value 5.

  • 3 < 5, so the target must be in the left subtree. Recurse left.

Step 2: Now at node 3. Compare key=3 with node value 3.

  • 3 == 3. We found the node to delete!

Step 3: Node 3 has two children (left=2, right=4). This is Case 3.

  • We need to find the inorder successor: the smallest value in the right subtree of node 3.

Step 4: Find inorder successor. Go to right child (4). Node 4 has no left child.

  • The inorder successor is node 4 (value = 4).

Step 5: Replace node 3's value with the successor's value.

  • Node value changes from 3 to 4.

Step 6: Recursively delete the successor (value 4) from the right subtree of the current node.

  • The right subtree of the current node was just the single node 4 (a leaf).
  • Deleting a leaf is Case 1: return null.
  • The current node's right child becomes null.

Step 7: The modified node (now value 4, left child 2, right child null) is returned to its parent (node 5).

  • Node 5's left child is now node 4.

Step 8: Return the root (5). Final tree: [5, 4, 6, 2, null, null, 7].

Recursive BST Deletion — Finding and Removing Node 3 — Watch how we use BST properties to navigate directly to the target node, then handle the two-children case by replacing with the inorder successor.

Algorithm

  1. Base case: If the root is null, return null (key not found).
  2. Search phase: Compare the key with the current node's value:
    • If key < node.val, recurse on the left subtree: node.left = deleteNode(node.left, key)
    • If key > node.val, recurse on the right subtree: node.right = deleteNode(node.right, key)
  3. Deletion phase (key == node.val):
    • Case 1 — No children: Return null (remove the leaf).
    • Case 2 — One child: Return the non-null child (bypass the node).
    • Case 3 — Two children:
      a. Find the inorder successor (smallest node in the right subtree).
      b. Replace the current node's value with the successor's value.
      c. Recursively delete the successor from the right subtree.
  4. Return the (possibly modified) current node.

Code

class Solution {
public:
    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 {
            // Found the node to delete
            
            // Case 1 & 2: No left child or no right child
            if (!root->left) {
                TreeNode* rightChild = root->right;
                delete root;
                return rightChild;
            }
            if (!root->right) {
                TreeNode* leftChild = root->left;
                delete root;
                return leftChild;
            }
            
            // Case 3: Two children
            // Find inorder successor (smallest in right subtree)
            TreeNode* successor = root->right;
            while (successor->left) {
                successor = successor->left;
            }
            
            // Replace value with successor's value
            root->val = successor->val;
            
            // Delete the successor from right subtree
            root->right = deleteNode(root->right, successor->val);
        }
        
        return root;
    }
};
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None
        
        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:
            # Found the node to delete
            
            # Case 1 & 2: Missing one or both children
            if not root.left:
                return root.right
            if not root.right:
                return root.left
            
            # Case 3: Two children
            # Find inorder successor (smallest in right subtree)
            successor = root.right
            while successor.left:
                successor = successor.left
            
            # Replace value with successor's value
            root.val = successor.val
            
            # Delete the successor from right subtree
            root.right = self.deleteNode(root.right, successor.val)
        
        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 {
            // Found the node to delete
            
            // Case 1 & 2: Missing one or both children
            if (root.left == null) {
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }
            
            // Case 3: Two children
            // Find inorder successor (smallest in right subtree)
            TreeNode successor = root.right;
            while (successor.left != null) {
                successor = successor.left;
            }
            
            // Replace value with successor's value
            root.val = successor.val;
            
            // Delete the successor from right subtree
            root.right = deleteNode(root.right, successor.val);
        }
        
        return root;
    }
}

Complexity Analysis

Time Complexity: O(h), where h is the height of the BST

Searching for the node takes O(h) time — we follow one path from the root down. Finding the inorder successor also takes O(h) in the worst case (traversing down the right subtree's leftmost path). The recursive deletion of the successor is another O(h) traversal. In total, we do at most 2-3 root-to-leaf traversals, each O(h).

For a balanced BST, h = O(log n), giving O(log n) time.
For a skewed BST (worst case), h = O(n), giving O(n) time.

Space Complexity: O(h)

The recursion stack depth equals the height of the tree. For a balanced BST this is O(log n). For a skewed BST this is O(n). No additional data structures are used beyond the recursion stack.