Recover Binary Search Tree

An inorder traversal of a valid BST must produce strictly ascending values. When exactly two nodes are swapped, that sequence exhibits either one inversion (if the swapped nodes were adjacent in the sorted order) or two inversions (if they were separated). Catching those inversion boundaries during the traversal pinpoints both misplaced nodes without altering a single pointer.

The theory behind it

BST — the ground this problem stands on. All BST problems

What BST is

A binary search tree is a binary tree that enforces a strict ordering rule at every node. Every value stored in a node's left branch must be smaller than the node itself, and every value in its right branch must be larger. Because this rule holds true everywhere down the tree, searching for a value does not require checking every branch. At each step, a single comparison lets you discard an entire half of the remaining nodes.

When to reach for it

Reach for a binary search tree when problems mention sorted tree structures, finding the kth smallest element, checking tree validity, or searching within a range of values. Signals include queries for the next greater element in a dynamic set, finding the lowest common ancestor in a sorted tree, or converting sorted arrays into height-balanced trees. When data must remain sorted while supporting continuous insertions and lookups, BST properties are the target.

How the pattern works

Use the ordering property to prune entire subtrees. When looking for a key, move left if the target is smaller than the current node, or move right if it is larger, stopping when values match or when reaching a null link. For validating a tree, do not merely compare a node to its immediate children; pass valid lower and upper value bounds down through recursive calls. Walking a valid binary search tree in-order visits all values in strictly increasing numerical order.