Sponsored
Sponsored
This approach involves traversing the tree recursively to find the node to be deleted. Once found, we handle it based on different cases: the node has no children, one child, or two children. For the two children case, replace the node with its inorder successor (minimum of the right subtree).
Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(h) due to recursion stack space.
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
7def deleteNode(root: TreeNode, key: int) -> TreeNode:
8 if not root:
9 return None
10 if key < root.val:
11 root.left = deleteNode(root.left, key)
12 elif key > root.val:
13 root.right = deleteNode(root.right, key)
14 else:
15 if not root.left:
16 return root.right
17 if not root.right:
18 return root.left
19 minLargerNode = getMin(root.right)
20 root.val = minLargerNode.val
21 root.right = deleteNode(root.right, minLargerNode.val)
22 return root
23
24def getMin(node):
25 while node.left:
26 node = node.left
27 return nodeThis implementation of BST node deletion is recursive and handles various node configurations, replacing the target node with its inorder successor if it has two children.
This method uses an iterative approach with a stack to traverse and manipulate the binary search tree. By applying the concept of replacing with the inorder successor, this method ensures the tree's properties remain intact after deletion.
Time Complexity: O(h), where h is tree height.
Space Complexity: O(1) since no additional data structures are used.
1TreeNode* deleteNode(TreeNode* root, int key) {
TreeNode** cur = &root, **back = nullptr;
while (*cur && (*cur)->val != key)
cur = key < (*cur)->val ? &(*cur)->left : &(*cur)->right;
if (*cur) removeNode(cur);
return root;
}
void removeNode(TreeNode** node) {
TreeNode* toDelete = *node;
if (!(*node)->left)
*node = (*node)->right;
else if (!(*node)->right)
*node = (*node)->left;
else {
TreeNode** successor = &(*node)->right;
while ((*successor)->left) successor = &(*successor)->left;
(*node)->val = (*successor)->val;
removeNode(successor);
}
delete toDelete;
}This C++ method employs double pointers to iterate and modify the tree structure. This allows for a more direct and less recursive approach to node deletion.