Delete Node in a BST

LeetCode 450 | Difficulty: Medium

Medium

Problem Description

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.

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, 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: Could you solve it with time complexity O(height of tree)?

Topics: Tree, Binary Search Tree, Binary Tree

---

Solutions

Solution 1: C# (Best: 114 ms)

Metric	Value
Runtime	114 ms
Memory	39.6 MB
Date	2021-11-22

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode DeleteNode(TreeNode root, int key) {
        
    if(root == null) return root;
    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 rightSmallest = root.right;
        while(rightSmallest.left != null) rightSmallest = rightSmallest.left;
        rightSmallest.left = root.left;
        return root.right;
    }
    
    return root;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.