Recover Binary Search Tree - Solution & Explanation

Problem Overview: You are given the root of a Binary Search Tree where exactly two nodes were swapped by mistake. The structure of the tree is unchanged, but the BST property is violated. Your task is to recover the tree by swapping those two nodes back without changing the tree structure.

A valid binary search tree produces a strictly increasing sequence during an inorder traversal. When two nodes are swapped, this sorted order breaks at one or two positions. The key idea behind most solutions is to detect these violations during traversal and identify the two misplaced nodes.

Approach 1: In-Order Traversal with Additional Space (O(n) time, O(n) space)

This approach performs a standard inorder traversal and stores the visited node values in an array. Because inorder traversal of a BST should produce a sorted sequence, you can scan the array to find the two elements that violate the sorted order. Typically, the first violation marks the first misplaced node, and the second violation identifies the second node. After locating them, swap their values in the original tree.

The algorithm works in three phases: perform inorder traversal, detect the two incorrect values by comparing adjacent elements, then traverse the tree again to swap those values. The logic is straightforward and easy to reason about, making it a good starting point for understanding the problem. However, it requires extra memory proportional to the number of nodes because the entire traversal result is stored.

Approach 2: Morris Traversal for Constant Space Complexity (O(n) time, O(1) space)

This method removes the need for recursion or auxiliary arrays by using Morris traversal, a technique that temporarily modifies the tree to simulate depth-first search. Instead of using a stack, the algorithm creates temporary "threads" between nodes so you can return to a parent after finishing its left subtree.

While performing the inorder traversal, keep track of the previous visited node. Whenever prev.val > current.val, a BST violation occurs. The first violation identifies the first misplaced node, and the second violation identifies the second node. After completing the traversal, swap the values of these two nodes to restore the BST property.

Morris traversal maintains the inorder visiting order while using constant extra memory. The tree is restored to its original structure after traversal because temporary links are removed. This approach is considered optimal since it achieves O(n) time and O(1) auxiliary space.

Recommended for interviews: Interviewers usually expect the constant space solution. Starting with the simple inorder traversal approach demonstrates understanding of BST properties and debugging techniques. Following it with the Morris traversal optimization shows deeper knowledge of tree traversal algorithms and memory-efficient design. Being able to detect swapped nodes during a single traversal is the key insight tested in most interviews involving tree and BST problems.