Modify Structure

What is this?

Here you change a BST — add a node, remove one, or fix a broken one — without ruining the left-smaller, right-larger rule. Reading a sorted tree is easy; the skill is editing it so it stays sorted. As long as every value keeps its proper place, the tree still works like a sorted list you can search instantly.

💡 Fun fact: Deleting a node with two children is the famously tricky case. The fix is to swap it with its inorder successor — the smallest value in its right subtree — which is guaranteed to slot in without disturbing the order.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: Reading a BST is easy; changing one without breaking the ordering invariant is where the real care lives. Every edit here is the same discipline — first find the node by descending on comparisons, then restructure locally while guaranteeing that smaller-left and larger-right still holds for the whole tree. The hard part is never the search; it is the surgery that keeps the invariant intact.

The pattern

All three problems start with the familiar O(h) descent: compare against the node, go left or right. What differs is what you do when you arrive. Insertion finds an empty slot and hangs a node there. Deletion has to fill the hole left behind without scrambling order. Repair walks the whole tree to spot where order was already violated.

The unifying idea is the inorder successor — the next-largest key, found by stepping right once and then left as far as possible. It is the value that can safely replace a deleted node, and the inorder traversal it comes from is also what exposes a corrupted tree. Master "find the successor" and "preserve the sorted inorder sequence" and the chapter falls into place.

The problems

• Insert into a Binary Search Tree — the gentle case. Walk down to the leaf slot where the key belongs (left when smaller, right when larger) and attach a new node there. No existing node moves, so the invariant is preserved for free.
• Delete Node in a BST — the centerpiece, with three cases. A leaf is simply removed; a node with one child is replaced by that child; a node with two children is replaced by its inorder successor (smallest key in the right subtree), then that successor is deleted from where it originally sat. The successor swap is what keeps the ordering valid.
• Recover Binary Search Tree — two nodes were swapped by mistake; restore the tree. An inorder traversal of a valid BST is strictly increasing, so the swap shows up as one or two out-of-order dips. Identify the two offending nodes, swap their values back, and you are done — no restructuring needed.

Key takeaways

• Find first, then restructure — the search is the easy part; protecting the invariant during the edit is the skill.
• Insertion attaches at a leaf slot, so no existing node ever has to move.
• Deletion has three cases; the two-child case hinges on the inorder successor swap.
• The inorder successor is the right-once-then-left-all-the-way node — learn it once, reuse it everywhere.
• Recovery rides the inorder sequence: a valid BST is strictly increasing, so swapped nodes appear as out-of-order dips.
• Most edits stay O(h); only the full repair scan touches every node in O(n).

Order: Insert into a Binary Search Tree → Delete Node in a BST → Recover Binary Search Tree.