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 - 1O(n) space is pretty straight-forward. Could you devise a constant O(1) space solution?In a valid Binary Search Tree (BST), an inorder traversal always produces a sorted sequence. In this problem, exactly two nodes are swapped by mistake, breaking that sorted order. The key idea is to perform an inorder traversal and detect the positions where the ordering rule prev.val <= current.val is violated.
While traversing, track the previous node and identify the two nodes that break the sorted property. The first incorrect node appears when the previous value is greater than the current value, and the second node appears at the later violation. After the traversal, swapping their values restores the BST structure without modifying the tree shape.
This approach typically uses Depth-First Search (DFS) with recursion and runs in O(n) time since every node is visited once. The space complexity is O(h) due to the recursion stack, where h is the tree height. An advanced optimization uses Morris Traversal to achieve O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS Inorder Traversal | O(n) | O(h) |
| Morris Traversal (Optimized) | O(n) | O(1) |
NeetCode
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.
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.
1class Solution:
2 def recoverTree(self, root: TreeNode) -> None:
3 def inorder(node):
4This 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.
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.
Time Complexity: O(n).
Space Complexity: O(1).
public void RecoverTree(TreeNode root) {
TreeNode first = null, second = null, prev = null;
TreeNode current = root;
while (current != null) {
if (current.left == null) {
if (prev != null && current.val < prev.val) {
second = current;
if (first == null) first = prev;
}
prev = current;
current = current.right;
} else {
TreeNode pre = current.left;
while (pre.right != null && pre.right != current) pre = pre.right;
if (pre.right == null) {
pre.right = current;
current = current.left;
} else {
pre.right = null;
if (prev != null && current.val < prev.val) {
second = current;
if (first == null) first = prev;
}
prev = current;
current = current.right;
}
}
}
int temp = first.val;
first.val = second.val;
second.val = temp;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or similar BST correction problems are common in FAANG and other top tech interviews. It tests understanding of BST properties, tree traversal, and space optimization techniques.
Yes, it can be solved using Morris Traversal, which performs inorder traversal without recursion or an explicit stack. This method temporarily modifies tree pointers to achieve O(1) auxiliary space.
The optimal approach is to use an inorder traversal of the BST to detect violations in the sorted order. By identifying the two misplaced nodes during traversal and swapping their values, the BST property can be restored in O(n) time.
The problem primarily uses a binary tree structure and leverages the BST property. Depth-First Search with inorder traversal is the most suitable technique to detect incorrect node placements.
This C# solution follows the Morris Traversal strategy, minimizing space usage by recompensing tree structure for the necessity of stack memory. It directly handles tree sequencing and discovers anomalies during traversal.