450. Delete Node in a BST


Problem Description

This problem involves modifying a Binary Search Tree (BST) by deleting a specific node with a given key. The BST has a property where for every node, the left children are less than the current node, and the right children are greater. The problem can be broken into two main parts:

  1. Locating the node that should be removed.
  2. Once the node is found, executing the removal process.

The complication in deletion comes from ensuring that the BST property is maintained after the node is removed. This means correctly rearranging the remaining nodes so that the tree remains a valid BST.

Intuition

The solution follows the property of BST. If the key to be deleted is less than the root node's key, then it lies in the left subtree. If the key to be deleted is greater than the root's key, then it lies in the right subtree. If the key is equal to the root's key, then the root is the node to be deleted.

For the deletion, there are three scenarios:

  1. Node with only one child or no child: If the node to be deleted has one or no children, we can simply replace the node with its child (if any) or set it to None.
  2. Node with two children: Find the inorder successor (smallest in the right subtree or largest in the left subtree) of the node. Copy the inorder successor's content to the node and delete the inorder successor. This is because inorder successors are always a leaf or have a single child, making them easier to remove.
  3. Leaf node: If the node is a leaf and needs to be deleted, we can simply remove the node from the tree.

The given solution first finds the node to delete, then based on its children, replaces the node accordingly. When a node with two children is deleted, instead of searching for the inorder predecessor, the algorithm finds the inorder successor, which is the smallest node in the right subtree, and swaps the values. Then the algorithm recursively deletes the successor node.

Solution Approach

The solution to the delete operation in a BST uses recursion to simplify the deletion process. Let's walk through the implementation approach:

  1. Base Case: If the root is None, there is nothing to delete, so we return None.

  2. Searching Phase: If the key is less than the root's value, we need to go to the left subtree: root.left = self.deleteNode(root.left, key) If the key is greater than the root's value, we need to go to the right subtree: root.right = self.deleteNode(root.right, key)

    Here, the algorithm is using recursion to traverse the tree in a BST property-aware manner (lesser values to the left, greater values to the right).

  3. Node Found: Once we find the node with the value equal to the key (i.e., root.val == key), we need to delete this node while keeping the tree structure.

    a. Node with One or No Child: If the node to be deleted has either no children (root.left is None and root.right is None) or one child, it can be deleted by replacing it with its non-null child or with None.

    If the left child is None, it means the node either has a right child or no child at all. Hence, we return root.right.

    If the right child is None, it means the node has a left child only, so we return root.left.

    b. Node with Two Children: If the node to be deleted has two children, we need to find the inorder successor of the node, which is the smallest node in the right subtree. We do this by traversing to the leftmost child in the right subtree.

    Once the inorder successor is found, we replace the node's value with the successor's value. In the code, this is accomplished by swapping the root node with its right child first and then attaching the original left subtree to the new root.

    Finally, we delete the inorder successor node which has been moved to the root position by calling delete on the right subtree: root.right = self.deleteNode(root.right, successor.val) (not explicitly shown in the given reference code but implied by the structure of the recursion).

This intuitive approach of handling different cases separately and utilizing the BST property ensures that the updated tree maintains its BST properties after the deletion is performed.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's use a small example to illustrate the solution approach. Consider the following BST where we want to delete the node with key 7:

1        5
2       / \
3      3   8
4         / \
5        7   9

Following the solution approach:

  1. Base Case: The root is not None, so we proceed with the operation.

  2. Searching Phase: The key 7 is greater than the root's value 5, so we examine the right subtree:

1    8
2   / \
3  7   9

Since 7 is lesser than 8, we now go to the left subtree of node 8, where we find our node with the value 7.

  1. Node Found: As the node’s key matches, we proceed with deletion.

a. Node with One or No Child: Node 7 is a leaf node in this scenario (no children). According to the third case, it can be simply removed from the tree. This means the left child of the node 8 will be set to None.

b. Node with Two Children: This does not apply here since our node 7 is a leaf.

Finally, the updated BST looks like this after deleting node 7:

1    5
2   / \
3  3   8
4       \
5        9

The BST properties are maintained, and 7 has been successfully removed.

Python Solution

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7
8class Solution:
9    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
10        # If the root is None, then there is nothing to delete, return None
11        if root is None:
12            return None
13
14        # If the key to be deleted is smaller than the root's key, 
15        # then it lies in the left subtree
16        if key < root.val:
17            root.left = self.deleteNode(root.left, key)
18            return root
19
20        # If the key to be deleted is greater than the root's key,
21        # then it lies in the right subtree
22        if key > root.val:
23            root.right = self.deleteNode(root.right, key)
24            return root
25
26        # If the key is the same as root's key, then this is the node to be deleted
27
28        # If the node has only one child or no child
29        if root.left is None:
30            return root.right
31
32        if root.right is None:
33            return root.left
34
35        # If the node has two children, get the inorder successor
36        # (smallest in the right subtree)
37        min_right_subtree = root.right
38        while min_right_subtree.left:
39            min_right_subtree = min_right_subtree.left
40
41        # Copy the inorder successor's content to this node
42        root.val = min_right_subtree.val
43
44        # Delete the inorder successor
45        root.right = self.deleteNode(root.right, min_right_subtree.val)
46
47        return root
48

Java Solution

1// Definition for a binary tree node.
2class TreeNode {
3    int val;
4    TreeNode left;
5    TreeNode right;
6
7    // Constructor with no arguments
8    TreeNode() {}
9
10    // Constructor with value only
11    TreeNode(int val) { this.val = val; }
12
13    // Constructor with value, left, and right child nodes
14    TreeNode(int val, TreeNode left, TreeNode right) {
15        this.val = val;
16        this.left = left;
17        this.right = right;
18    }
19}
20
21class Solution {
22  
23    // Function to delete a node with a given key from a binary search tree
24    public TreeNode deleteNode(TreeNode root, int key) {
25        // Base case: if the root is null, return null
26        if (root == null) {
27            return null;
28        }
29
30        // If the key is smaller than root's value, delete in the left subtree
31        if (root.val > key) {
32            root.left = deleteNode(root.left, key);
33            return root;
34        }
35      
36        // If the key is greater than root's value, delete in the right subtree
37        if (root.val < key) {
38            root.right = deleteNode(root.right, key);
39            return root;
40        }
41      
42        // If the root itself is the node to be deleted
43
44        // If the root has no left child, return the right child directly
45        if (root.left == null) {
46            return root.right;
47        }
48      
49        // If the root has no right child, return the left child directly
50        if (root.right == null) {
51            return root.left;
52        }
53      
54        // If the root has both left and right children
55        TreeNode successor = root.right;
56      
57        // Find the successor (smallest in the right subtree)
58        while (successor.left != null) {
59            successor = successor.left;
60        }
61      
62        // Move the left subtree of the root to the left of the successor
63        successor.left = root.left;
64      
65        // The new root should be the right child of the deleted node
66        root = root.right;
67      
68        // Return the modified tree
69        return root;
70    }
71}
72

C++ Solution

1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    TreeNode* deleteNode(TreeNode* root, int key) {
16        // If root is null, return immediately
17        if (!root) {
18            return root;
19        }
20
21        // If the key to be deleted is smaller than the root's value,
22        // then it lies in left subtree
23        if (root->val > key) {
24            root->left = deleteNode(root->left, key);
25            return root;
26        }
27
28        // If the key to be deleted is greater than the root's value,
29        // then it lies in right subtree
30        if (root->val < key) {
31            root->right = deleteNode(root->right, key);
32            return root;
33        }
34
35        // If key is the same as root's value, then this is the node
36        // to be deleted
37
38        // Node with only one child or no child
39        if (!root->left) {
40            return root->right;
41        }
42        if (!root->right) {
43            return root->left;
44        }
45
46        // Node with two children: Get the inorder successor (smallest
47        // in the right subtree)
48        TreeNode* successorNode = root->right;
49        while (successorNode->left) {
50            successorNode = successorNode->left;
51        }
52
53        // Copy the inorder successor's content to this node
54        root->val = successorNode->val;
55      
56        // Delete the inorder successor since its value is now copied 
57        root->right = deleteNode(root->right, successorNode->val);
58
59        return root;
60    }
61};
62

Typescript Solution

1/**
2 * Definition for a binary tree node.
3 */
4interface TreeNode {
5  val: number;
6  left: TreeNode | null;
7  right: TreeNode | null;
8}
9
10/**
11 * Deletes a node with the specified key from the binary search tree.
12 * @param {TreeNode | null} root - The root of the binary search tree.
13 * @param {number} key - The value of the node to be deleted.
14 * @returns {TreeNode | null} - The root of the binary search tree after deletion.
15 */
16function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
17  // If the root is null, return null (base case).
18  if (root === null) {
19      return root;
20  }
21
22  // Check if the key to delete is smaller or greater than the root's value to traverse the tree.
23  if (root.val > key) {
24      // The key to be deleted is in the left subtree.
25      root.left = deleteNode(root.left, key);
26  } else if (root.val < key) {
27      // The key to be deleted is in the right subtree.
28      root.right = deleteNode(root.right, key);
29  } else {
30      // When the node to be deleted is found
31      if (root.left === null && root.right === null) {
32          // Case 1: Node has no children (it is a leaf), simply remove it.
33          root = null;
34      } else if (root.left === null || root.right === null) {
35          // Case 2: Node has one child, replace the node with its child.
36          root = root.left || root.right;
37      } else {
38          // Case 3: Node has two children.
39          if (root.right.left === null) {
40              // If the immediate right child has no left child, promote the right child.
41              root.right.left = root.left;
42              root = root.right;
43          } else {
44              // If the right child has a left child, find the in-order predecessor.
45              let minPredecessorNode = root.right;
46              while (minPredecessorNode.left && minPredecessorNode.left.left !== null) {
47                  minPredecessorNode = minPredecessorNode.left;
48              }
49              // Replace the root's value with the in-order predecessor's value.
50              const minValue = minPredecessorNode.left.val;
51              root.val = minValue;
52              // Delete the in-order predecessor.
53              minPredecessorNode.left = deleteNode(minPredecessorNode.left, minValue);
54          }
55      }
56  }
57
58  // Return the updated root.
59  return root;
60}
61

Time and Space Complexity

Time Complexity

The time complexity of the given code for deleting a node from a BST (Binary Search Tree) depends on the height of the tree h.

  1. Finding the node to delete takes O(h) time since in the worst case, we might have to traverse from the root to the leaf.
  2. The deletion process itself is O(1) for nodes with either no child or a single child.
  3. For nodes with two children, we find the minimum element in the right subtree, which also takes O(h) time in the worst case (when the tree is skewed).

Therefore, the overall time complexity is O(h), which would be O(log n) for a balanced BST and O(n) for a skewed BST (where n is the number of nodes).

Space Complexity

The space complexity of the code is determined by the maximum amount of space used at any one time during the recursive calls (the call stack size).

  1. The maximum depth of recursive calls is equal to the height h of the tree.
  2. There are no additional data structures used that grow with the input size.

The space complexity is therefore O(h), which corresponds to O(log n) for a balanced BST and O(n) for a skewed BST due to the recursive function calls.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫