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:
- Locating the node that should be removed.
- 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:
- 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. - 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.
- 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.
Learn more about Tree, Binary Search Tree and Binary Tree patterns.
How many ways can you arrange the three letters A, B and C?
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:
-
Base Case: If the root is
None, there is nothing to delete, so we returnNone. -
Searching Phase: If the
keyis less than the root's value, we need to go to the left subtree:root.left = self.deleteNode(root.left, key)If thekeyis 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).
-
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.leftisNoneandroot.rightisNone) or one child, it can be deleted by replacing it with its non-null child or withNone.If the left child is
None, it means the node either has a right child or no child at all. Hence, we returnroot.right.If the right child is
None, it means the node has a left child only, so we returnroot.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.
Which data structure is used to implement priority queue?
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:
-
Base Case: The root is not
None, so we proceed with the operation. -
Searching Phase: The key
7is greater than the root's value5, 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.
- 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.
Solution Implementation
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
481// 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}
721/**
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};
621/**
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}
61Which of the following problems can be solved with backtracking (select multiple)
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.
- 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. - The deletion process itself is
O(1)for nodes with either no child or a single child. - 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).
- The maximum depth of recursive calls is equal to the height
hof the tree. - 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.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
Binary Search Tree Intro Definition A Binary Search Tree or BST is a rooted binary tree with the value of each internal node being greater than all the values in the respective node's left subtree and less than the ones in its right subtree An empty tree is a BST since it satisfies the
Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node
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.