BST Operations
Beyond search and insertion, BST supports deletion, finding min/max, and checking validity. These operations rely on the BST property.
1. Find Minimum and Maximum
Min: keep going left until null. Max: keep going right.
public TreeNode findMin(TreeNode root) {
while (root.left != null) root = root.left;
return root;
}
public TreeNode findMax(TreeNode root) {
while (root.right != null) root = root.right;
return root;
}
2. Deletion in BST
Three cases:
a) Leaf node – just remove.
b) Node with one child – replace with child.
c) Node with two children – find inorder successor (min in right subtree), copy its value to node, then delete successor.
public TreeNode delete(TreeNode root, int key) {
if (root == null) return null;
if (key < root.val) root.left = delete(root.left, key);
else if (key > root.val) root.right = delete(root.right, key);
else {
// node to delete found
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// two children
TreeNode minNode = findMin(root.right);
root.val = minNode.val;
root.right = delete(root.right, minNode.val);
}
return root;
}
3. Check if a tree is a BST
Use inorder traversal and check if previous value is less than current.
Two Minute Drill
- Min/Max: traverse left/right.
- Deletion: three cases; O(log n) average.
- Successor/predecessor can be found for any node.
- BST validity check via inorder or range constraints.
Need more clarification?
Drop us an email at career@quipoinfotech.com