BST operations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

                     [ 8 ]
                   /       \
              [ 3 ]         [ 10 ]
             /     \              \
          [ 1 ]   [ 6 ]           [ 14 ]
                 /     \          /
               [ 4 ]   [ 7 ]   [ 13 ]

Search for Key = 7:
1. Compare 7 with Root 8: 7 < 8 -> Go LEFT to 3!  (Discard entire right half!)
2. Compare 7 with 3:      7 > 3 -> Go RIGHT to 6! (Discard left half of 3!)
3. Compare 7 with 6:      7 > 6 -> Go RIGHT to 7!
4. Found 7 in 3 comparisons instead of scanning all 8 nodes!

Average Time: O(log N) | Worst Time (unbalanced): O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// BST Search: O(log n) average, O(n) worst
public TreeNode searchBST(TreeNode root, int val) {
    if (root == null || root.val == val) return root;
    if (val < root.val) return searchBST(root.left, val);
    return searchBST(root.right, val);
}

// BST Insert: O(log n) average
public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);
    if (val < root.val) {
        root.left = insertIntoBST(root.left, val);
    } else {
        root.right = insertIntoBST(root.right, val);
    }
    return root;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

CASE 1: Node has NO children (Leaf Node):
Simply unlink and return null.
    [ 5 ]                 [ 5 ]
   /     \       ->      /
 [ 2 ]   [ 8 ]         [ 2 ]  (8 removed)

CASE 2: Node has ONE child:
Bypass the node and connect parent directly to child.
    [ 5 ]                 [ 5 ]
   /     \       ->      /     \
 [ 2 ]   [ 8 ]         [ 2 ]   [ 9 ]  (8 replaced with 9)
           \
           [ 9 ]

CASE 3: Node has TWO children:
Find the IN-ORDER SUCCESSOR (smallest node in the right subtree).
Copy successor's value into the target node, then delete the successor!
Target node to delete: [ 5 ]
         [ 5 ]                        [ 6 ] (Successor copied!)
       /       \                    /       \
    [ 2 ]     [ 8 ]       ->      [ 2 ]     [ 8 ]
             /     \                        /     \
   Successor:[ 6 ] [ 9 ]                 (deleted) [ 9 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public TreeNode deleteNode(TreeNode root, int key) {
    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 {
        // Found the node to delete!
        // Case 1 & 2: Zero or one child
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;

        // Case 3: Two children
        // Find in-order successor (minimum in right subtree)
        TreeNode successor = findMin(root.right);
        root.val = successor.val; // Copy successor's value
        // Recursively delete the successor from the right subtree
        root.right = deleteNode(root.right, successor.val);
    }
    return root;
}

private TreeNode findMin(TreeNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}