Recover Binary Search Tree - Video Solutions

Problem Overview: A valid Binary Search Tree (BST) has an in-order traversal that produces a sorted sequence. In this problem, exactly two nodes in the BST were swapped by mistake. Your task is to restore the tree without changing its structure by identifying those two nodes and swapping their values back.

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

A straightforward approach is to perform an in-order traversal and store all node references in an array. Because a correct BST produces a sorted order, any swapped nodes will appear as violations where prev.val > curr.val. Iterate through the collected list and record the two positions where this ordering breaks. The first incorrect node is the larger value from the first violation, and the second node is the smaller value from the last violation. After identifying both nodes, swap their values to recover the BST. This method is simple and easy to reason about but uses O(n) additional memory to store the traversal.

This approach relies heavily on properties of a Binary Search Tree and uses a standard Depth-First Search traversal to collect nodes in sorted order.

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

The optimal approach performs the same in-order traversal but without recursion or an auxiliary array. Morris Traversal temporarily modifies the tree structure by creating threaded links to predecessor nodes. While traversing, keep track of the previous visited node and detect ordering violations where prev.val > curr.val. The first time this happens, store prev as the first misplaced node. For the second violation, store curr as the second node. After the traversal finishes, swap the values of these two nodes.

Morris Traversal works because it simulates the call stack used in recursive tree traversal by reusing null pointers as temporary links. Each edge is visited at most twice, keeping the time complexity at O(n) while reducing space usage to O(1). This makes it ideal when memory constraints matter or when interviewers specifically ask for constant space.

Recommended for interviews: Start by explaining the in-order traversal idea since it directly leverages the sorted property of BSTs. That shows you understand the core invariant. Then move to Morris Traversal as the optimized solution with O(1) extra space. Interviewers usually expect the constant-space approach because it demonstrates deeper knowledge of tree traversal techniques.