Visualize binary search trees, node path traversals, element insertions, and structural node deletions.
Where h is the height of the tree. Finding the successor or predecessor in Case 3 requires traversing the right child's left spine.
Recursively rebuilds subtrees from leaf to pivot point, requiring O(h) call stack memory.
Node delete(Node root, int key) {if (root == null) return null;
if (key < root.key) root.left = delete(root.left, key);
else if (key > root.key) root.right = delete(root.right, key);
else {if (root.left == null) return root.right;
if (root.right == null) return root.left;
Node succ = getSuccessor(root.right);
root.key = succ.key;
root.right = delete(root.right, succ.key);
}
return root;
}