Search, Insert, Delete

The One Property That Makes BSTs Work

A binary search tree has exactly one rule:

For every node, all values in its left subtree are smaller, and all values in its right subtree are larger.

This isn't a local check — it's a global invariant maintained locally. Node 5 doesn't just need its immediate children 3 and 7 to be in order. It needs every descendant on the left to be less than 5, and every descendant on the right to be greater.

Read the tree left to right: 2, 3, 4, 5, 6, 7, 8. Sorted. That's not a coincidence — it's the BST property in action. Inorder traversal of a BST always gives sorted order. We'll exploit that heavily in the next two lessons.

Search: Binary Search, But on a Tree

You want to find whether 6 exists in the tree above.

Start at the root (5). Is 6 equal to 5? No. Is 6 < 5? No. So 6 must be in the right subtree. Move to 7. Is 6 < 7? Yes. Move left to 6. Found it.

At each node, you eliminate an entire subtree. If the tree is balanced, that's half the nodes gone per step — \(O(\log n)\). If the tree is a chain (worst case), it's \(O(n)\).

TreeNode* searchBST(TreeNode* root, int target) {
    if (!root) return nullptr;
    if (target < root->value) return searchBST(root->left, target);
    if (target > root->value) return searchBST(root->right, target);
    return root;
}

Three branches. Target is smaller — go left. Target is larger — go right. Target matches — you're done.

Insert: Search Until You Fall Off

Inserting 4.5 into the BST means finding where 4.5 would be if it existed, then creating a node there.

Start at 5: 4.5 < 5, go left. At 3: 4.5 > 3, go right. At 4: 4.5 > 4, go right. Right child is nullptr — that's where 4.5 belongs.

The code looks almost identical to search. The only difference: when you hit nullptr, instead of returning "not found," you create the new node.

TreeNode* insertIntoBST(TreeNode* root, int value) {
    if (!root) return new TreeNode(value);
    if (value < root->value) root->left = insertIntoBST(root->left, value);
    else root->right = insertIntoBST(root->right, value);
    return root;
}

Notice the pattern: root->left = insertIntoBST(root->left, value). The recursive call returns the (possibly new) subtree, and the parent links to it. This "return the modified subtree" trick handles the nullptr case naturally.

Delete: The Hard One

Deletion has three cases, and the third one trips everyone up.

We want to delete a node from the BST while maintaining the BST property. Consider deleting from this tree:

Case 1: Deleting a Leaf

Delete 2. It has no children. Just remove it. Set its parent's pointer to nullptr.

Case 2: Deleting a Node with One Child

Delete 3 (which now has only right child 4). Bypass it — connect 5's left pointer directly to 4.

The BST property holds because 4 was already in the left subtree of 5.

The three deletion cases: leaf, one child, and two children

Case 3: Deleting a Node with Two Children

Delete 7. It has two children: 6 and 8. You can't just remove it — both children need a parent.

The fix: find the inorder successor of 7. That's the smallest node in 7's right subtree — in this case, 8. Copy 8's value into the 7 slot, then delete the original 8 node (which is now a leaf or has one child — cases 1 or 2).

Before:     5            After:      5
           / \                      / \
          4   7                    4   8
             / \                      /
            6   8                    6

Why the inorder successor? Because it's the smallest value that's larger than 7. Putting it in 7's place preserves the BST property: everything in the left subtree (6) is still smaller, everything else in the right subtree is still larger.

You could also use the inorder predecessor (largest value in the left subtree). Both work.

Inorder successor replaces the deleted node to maintain BST property

Full Trace: Deleting 5 (the Root)

Delete 5 from the original tree:

Step 1: Node 5 has two children → Case 3. Find inorder successor: go right to 7, then go left as far as possible. 7's left child is 6. 6 has no left child. Inorder successor = 6.

Step 2: Copy 6's value into the root node.

Step 3: Delete the original 6 from the right subtree. 6 is a leaf → Case 1.

Step	Action	Tree State
Start	Delete 5	`5(3(2,4), 7(6,8))`
Find successor	Smallest in right subtree = 6	—
Copy value	Replace 5 with 6	`6(3(2,4), 7(6,8))`
Delete original 6	Leaf removal	`6(3(2,4), 7(nil,8))`

Result:

Verify the BST property: inorder gives 2, 3, 4, 6, 7, 8. Sorted. Correct.

The Code

TreeNode* findMin(TreeNode* root) {
    while (root->left) root = root->left;
    return root;
}

TreeNode* deleteNode(TreeNode* root, int target) {
    if (!root) return nullptr;

    if (target < root->value) {
        root->left = deleteNode(root->left, target);
    } else if (target > root->value) {
        root->right = deleteNode(root->right, target);
    } else {
        if (!root->left) return root->right;
        if (!root->right) return root->left;

        TreeNode* successor = findMin(root->right);
        root->value = successor->value;
        root->right = deleteNode(root->right, successor->value);
    }
    return root;
}

The else block handles all three cases. No left child? Return right (covers leaf + one-child). No right child? Return left. Both children? Find successor, copy, delete successor from right subtree.

Complexity: \(O(h)\) for all three operations, where \(h\) is the tree height. Balanced tree: \(O(\log n)\). Skewed tree: \(O(n)\).

Floor and Ceil: Search Variants

Floor of a value \(x\): the largest element in the BST that is \(\leq x\).

Ceil of a value \(x\): the smallest element in the BST that is \(\geq x\).

These are search with a twist. For floor: if you go right (current value is too small), the current node is a candidate — it might be the floor. If you go left (current value is too large), the current node is definitely not the floor.

int floorBST(TreeNode* root, int target) {
    int result = -1;
    while (root) {
        if (root->value == target) return target;
        if (root->value < target) {
            result = root->value;
            root = root->right;
        } else {
            root = root->left;
        }
    }
    return result;
}

Ceil is the mirror: update the candidate when you go left.

Try It

The starter code has a deleteNode function with a TODO. Build the tree, delete 7, and print the inorder traversal to verify.

Predict before running: If you delete the root of a single-node tree, what does deleteNode return? Trace: target == root->value, no left child, no right child. Returns root->right which is nullptr. Correct — the tree becomes empty.

Challenge: What happens if you delete a value that doesn't exist in the tree? Trace through the code. (Answer: the recursion reaches nullptr, returns nullptr, and nothing changes.)

Challenge 2: Implement insertIntoBST iteratively (no recursion). You'll need a parent pointer to link the new node.

Edge Cases to Watch For

Delete a node with two children where the successor has a right child: The successor is the leftmost node in the right subtree. If that successor itself has a right child, deleting the successor is Case 2 (one child), not Case 1 (leaf). You must handle this by recursively deleting the successor from the right subtree, not by simply removing it.

Problems

Problem	Link	Difficulty
LC 700 — Search in a BST	leetcode.com/problems/search-in-a-binary-search-tree	Easy
LC 701 — Insert into a BST	leetcode.com/problems/insert-into-a-binary-search-tree	Medium
LC 450 — Delete Node in a BST	leetcode.com/problems/delete-node-in-a-bst	Medium