You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
Example 1:
Input: root = [1,3,null,null,2] Output: [3,1,null,null,2] Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.
Example 2:
Input: root = [3,1,4,null,null,2] Output: [2,1,4,null,null,3] Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.
Constraints:
[2, 1000].-231 <= Node.val <= 231 - 1Follow up: A solution using
O(n) space is pretty straight-forward. Could you devise a constant O(1) space solution?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.
This approach uses an additional list to store the nodes during an in-order traversal of the BST. The in-order traversal yields the values of the BST in a sorted manner for a correct BST configuration. If two nodes have been swapped, this sorted order will be violated in exactly two places. By storing all nodes during traversal and comparing them, we can identify the two swapped nodes. Once identified, we swap their values to correct the tree.
This method requires O(n) space to store the nodes' values where n is the number of nodes in the tree.
This Python solution performs an in-order traversal of the BST and stores the nodes in a list. It then iterates through this list to find the two nodes that are out of order, i.e., the swapped nodes, by checking where the current node value is less than the previous node value. Finally, it swaps the values of these nodes to correct the BST.
Time Complexity: O(n) since we are conducting an in-order traversal of the tree.
Space Complexity: O(n) as we store nodes in a list for comparison.
This approach leverages Morris Traversal to achieve O(1) space complexity, without needing an auxiliary stack or recursion. Morris Traversal utilizes the tree structure itself to keep track of nodes and ensures the tree is reset to its original configuration after traversal. To correct the BST, we detect swapped nodes by identifying violation of BST properties during traversal, and then we swap these nodes to achieve a valid BST.
This Python solution uses Morris Inorder Traversal, which leverages the threads in the tree structure to avoid using additional space. While traversing, we establish temporary links (threads) to visiting nodes using their predecessor relations. We detect unordered node pairs and correct them by swapping their values.
Time Complexity: O(n).
Space Complexity: O(1).
In-order traversal of a binary search tree results in an increasing sequence. If two nodes' values are mistakenly swapped, there will definitely be two reverse pairs in the sequence obtained from the in-order traversal. We use first and second to record the smaller and larger values of these two reverse pairs, respectively. Finally, swapping the values of these two nodes will correct the mistake.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary search tree.
| Approach | Complexity |
|---|---|
| In-Order Traversal with Additional Space | Time Complexity: O(n) since we are conducting an in-order traversal of the tree. |
| Morris Traversal for Constant Space Complexity | Time Complexity: O(n). |
| In-order Traversal | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| In-Order Traversal with Array | O(n) | O(n) | Best for clarity and quick implementation when extra memory is acceptable. |
| Morris Traversal (Constant Space) | O(n) | O(1) | Preferred in interviews when constant auxiliary space is required. |
Recover Binary Search Tree (with Follow Up) | Live Coding with Explanation | Leetcode #99 • Algorithms Made Easy • 15,958 views views
Watch 9 more video solutions →Practice Recover Binary Search Tree with our built-in code editor and test cases.
Practice on FleetCode