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:
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:
[0, 104]
.-105 <= Node.val <= 105
root
is a valid binary search tree.-105 <= key <= 105
Follow up: Could you solve it with time complexity O(height of tree)
?
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force approach to deleting a node in a Binary Search Tree is like completely rebuilding the tree without the node you want to remove. It involves exploring every possible tree structure after deletion to find a valid one. Think of it as starting from scratch and trying every way to arrange the remaining nodes.
Here's how the algorithm would work step-by-step:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def delete_node_brute_force(root, key_to_delete):
# Collect all nodes except the one to delete
remaining_nodes = []
def inorder_traversal(node):
if node:
inorder_traversal(node.left)
if node.value != key_to_delete:
remaining_nodes.append(node.value)
inorder_traversal(node.right)
inorder_traversal(root)
if not remaining_nodes:
return None
best_tree = None
# Try all possible arrangements of remaining nodes
import itertools
for permutation in itertools.permutations(remaining_nodes):
new_root = construct_bst(permutation)
if is_valid_bst(new_root):
best_tree = new_root
#Choose the first valid BST
break
return best_tree
def construct_bst(nodes):
if not nodes:
return None
root_value = nodes[0]
root = Node(root_value)
for value in nodes[1:]:
insert_node(root, value)
return root
def insert_node(root, value):
if value < root.value:
if root.left is None:
root.left = Node(value)
else:
insert_node(root.left, value)
else:
if root.right is None:
root.right = Node(value)
else:
insert_node(root.right, value)
def is_valid_bst(root):
#Check if tree satisfies BST property
return is_valid_bst_helper(root, float('-inf'), float('inf'))
def is_valid_bst_helper(node, minimum, maximum):
if not node:
return True
if node.value <= minimum or node.value >= maximum:
return False
#Ensure that left subtree is valid and right subtree is valid
is_left_valid = is_valid_bst_helper(node.left, minimum, node.value)
is_right_valid = is_valid_bst_helper(node.right, node.value, maximum)
return is_left_valid and is_right_valid
To remove a node from a Binary Search Tree efficiently, we first locate the node. If found, we need to handle cases based on whether the node has children, strategically replacing it to maintain the BST properties.
Here's how the algorithm would work step-by-step:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def delete_node_bst(root, key_to_delete):
if not root:
return root
if key_to_delete < root.value:
root.left = delete_node_bst(root.left, key_to_delete)
elif key_to_delete > root.value:
root.right = delete_node_bst(root.right, key_to_delete)
else:
# Node with only one child or no child
if not root.left:
temporary_node = root.right
root = None
return temporary_node
elif not root.right:
temporary_node = root.left
root = None
return temporary_node
# Node with two children:
# Get the inorder successor
# (smallest in the right subtree)
smallest_value_in_right_subtree = find_min_value(root.right)
# Copy the inorder successor's
# content to this node
root.value = smallest_value_in_right_subtree
# Delete the inorder successor
# Because we copied its value up
root.right = delete_node_bst(root.right, smallest_value_in_right_subtree)
return root
def find_min_value(root):
current_node = root
# Find leftmost leaf
while(current_node.left is not None):
current_node = current_node.left
return current_node.value
Case | How to Handle |
---|---|
Root is null (empty tree) | Return null immediately as there is nothing to delete in an empty tree. |
Node to be deleted is the root and has no children | Return null, effectively deleting the entire tree. |
Node to be deleted is the root and has only a left child | Return the left child as the new root. |
Node to be deleted is the root and has only a right child | Return the right child as the new root. |
Node to be deleted has two children; find the inorder successor in the right subtree. | Replace the node to be deleted with its inorder successor and delete the successor from the right subtree. |
Node to be deleted is not found in the tree. | Return the original root without modification to avoid unintended side effects. |
Tree contains duplicate keys, and we want to delete one specific instance. | Ensure comparison checks for equality, handles identical values, and deletes the correct node (usually the first found according to the traversal). |
Deeply unbalanced tree can lead to stack overflow with recursive solutions. | Consider iterative solution if recursion depth is a potential concern. |