Delete Node in a BST - Practice Coding Problems

Delete Node in a BST - Problem

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:

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

There are three cases to consider when deleting a node:

Node has no children (leaf node): Simply remove it
Node has one child: Replace the node with its child
Node has two children: Replace the node with its inorder successor (or predecessor)

Input & Output

Example 1 — Node with Two Children

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

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

💡 Note: Node 3 has two children (2 and 4). Replace it with inorder successor 4, then delete original 4.

Example 2 — Leaf Node

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

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

💡 Note: Node 2 is a leaf node (no children), so simply remove it from the tree.

Example 3 — Root Node Deletion

$ Input: root = [7], key = 7

› Output: []

💡 Note: Deleting the only node in the tree results in an empty tree.

Constraints

The number of nodes in the tree is in the range [0, 10⁴]
-10⁵ ≤ Node.val ≤ 10⁵
Each node has a unique value
-10⁵ ≤ key ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input BST

Binary Search Tree with target key to delete

Search & Delete

Find node using BST property and apply deletion rules

Output BST

Resulting BST after deletion with structure preserved

Key Takeaway

🎯 Key Insight: Use BST property for O(log n) search and replace nodes with two children using their inorder successor

Asked in

G Google 45 a Amazon 38 M Microsoft 32 A Apple 28

The key insight is to leverage the BST property for efficient O(log n) search and handle three deletion cases: no children (remove directly), one child (replace with child), and two children (replace with inorder successor). Best approach uses recursive BST deletion with Time: O(log n), Space: O(log n).

Common Approaches

Approach	Time	Space	Notes
✓ BST Property Search with Recursive Deletion	O(log n)	O(log n)	Use BST property to find node efficiently and handle three deletion cases
Brute Force Traversal	O(n log n)	O(n)	Search entire tree linearly and reconstruct without target node

BST Property Search with Recursive Deletion — Algorithm Steps

Step 1: Search for target node using BST property
Step 2: Handle deletion based on number of children
Step 3: For two children case, replace with inorder successor

Visualization

Tap to expand

Step-by-Step Walkthrough

Search Phase

Use BST property to find target node efficiently

Case Analysis

Determine number of children (0, 1, or 2)

Replacement

Replace with inorder successor for two-child case

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

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

int* solution(struct TreeNode* root, int key, int* returnSize) {
    root = deleteNode(root, key);
    *returnSize = 0;
    return NULL;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    fgets(line, sizeof(line), stdin);
    int key = atoi(line);
    
    int returnSize;
    int* result = solution(NULL, key, &returnSize);
    
    printf("[]");
    printf("\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

BST search takes O(log n) on average, O(n) worst case for skewed tree

⚡ Linearithmic

Space Complexity

O(log n)

Recursion stack depth equals tree height, O(log n) average case

⚡ Linearithmic Space

87.6K Views

High Frequency

~25 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BST Property Search with Recursive Deletion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler