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.
1 if (root == null) return null;
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;
TreeNode minNode = GetMin(root.right);
root.val = minNode.val;
root.right = DeleteNode(root.right, minNode.val);
}
return root;
}
private TreeNode GetMin(TreeNode node) {
while (node.left != null) node = node.left;
return node;
}In C#, the deletion process in a BST is performed recursively, taking care of all possible scenarios regarding node 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.
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, key):
8 dummy = TreeNode(0)
9 dummy.left = root
10 parent, node = dummy, root
11 while node and node.val != key:
12 parent = node
13 if key < node.val:
14 node = node.left
15 else:
16 node = node.right
17 if node:
18 if node.left and node.right:
19 minLargerNode, parent = node.right, node
20 while minLargerNode.left:
21 parent = minLargerNode
22 minLargerNode = minLargerNode.left
23 node.val = minLargerNode.val
24 node = minLargerNode
25 if node == parent.left:
26 parent.left = node.left if node.left else node.right
27 else:
28 parent.right = node.left if node.left else node.right
29 return dummy.leftThis iterative Python solution uses a dummy node to help bypass complications from root node deletion and ensures an effective, non-recursive approach.