1. Problem Summary
You’re given the root of a Binary Search Tree (BST) in which exactly two nodes’ values have been swapped by mistake. The tree structure (shape, parent-child links) is unchanged, but the BST ordering property is violated.
Your task: restore the BST by swapping the values of the two incorrect nodes back, without changing the tree structure (i.e., only swap node values).
Input: root of a BST with exactly two nodes’ values swapped.
Output: The tree corrected in-place (no return value, typically void).
Constraints:
Number of nodes: [2, 1000]
Values: [-231, 231 - 1]
Follow-up: Solve with O(1) extra space (besides recursion stack).
2. Examples Explanation
Example 1:
Input: root = [1,3,null,null,2]
Tree:
1
left → 3
right → 2
In a correct BST, the left child of 1 must be < 1, but here it’s 3 > 1.
If we swap the values of 1 and 3, tree becomes:
3
left → 1
right → 2
Now inorder traversal: [1, 2, 3] – valid BST.
Output: [3,1,null,null,2].
Example 2:
Input: root = [3,1,4,null,null,2]
Tree:
3
left → 1
right → 4
left → 2
In a correct BST, nodes in right subtree of 3 must be > 3, but 2 < 3 and is in that subtree.
Inorder traversal (current): [1, 3, 2, 4] – this violates the increasing order (3 > 2).
Correct BST would be [1, 2, 3, 4] → we can see 2 and 3 are swapped.
Swapping 2 and 3 fixes the tree:
2
left → 1
right → 4
left → 3
Output: [2,1,4,null,null,3].
3. Approach
Pattern:
This is a BST + inorder traversal problem. A valid BST has strictly increasing inorder sequence. When two values are swapped, that sequence has inversions (out-of-order pairs). We need to find those and swap the corresponding nodes back.
Naive / Straightforward Idea (O(n) Space):
Perform inorder traversal, collect all nodes in a list.
Extract their values into an array.
Sort the array.
Reassign sorted values back to nodes in inorder order.
Works but:
Time: O(n log n) because of sorting.
Space: O(n) because of list/array.
We can do better using BST properties and no extra array.
4. Better Approach: Detect Violations in Inorder
In a correct BST:
Inorder traversal yields v1 < v2 < v3 < ... < vn.
If two nodes’ values are swapped, say x and y, the inorder sequence will have 1 or 2 places where prev.val > current.val.
Cases:
Swapped nodes are not adjacent in inorder
Example correct: 1, 2, 3, 4, 5, 6
Swapped 2 and 5: 1, 5, 3, 4, 2, 6
Inversions:
5 > 3 → first violation: first = 5, middle = 3
4 > 2 → second violation: last = 2
Nodes to swap: first and last (5 and 2).
Swapped nodes are adjacent in inorder
Example correct: 1, 2, 3, 4
Swapped 2 and 3: 1, 3, 2, 4
Inversions:
3 > 2 → one violation: first = 3, middle = 2
No second violation.
Nodes to swap: first and middle (3 and 2).
Algorithm (inorder + pointers):
Maintain:
prev (previous node in inorder),
first, middle, last (potential swapped nodes).
Do inorder traversal:
For each current:
If prev != null and prev.val > current.val:
If first == null:
first = prev, middle = current
Else:
last = current
Update prev = current.
After traversal:
If last != null: swap first.val and last.val.
Else: swap first.val and middle.val.
This uses O(h) recursion stack, h is height.
Follow-up: O(1) Space with Morris Traversal:
To achieve strict O(1) extra space (no recursion, no stack), use Morris inorder traversal:
Temporarily modify tree pointers to simulate recursion.
Visit nodes in inorder with only O(1) extra space.
While traversing, apply the same prev/first/middle/last logic.
After traversal, revert tree modifications automatically via Morris procedure.
High-level Morris idea:
Let current = root.
While current != null:
If current.left == null:
Visit current (apply detection logic).
Move current = current.right.
Else:
Find the rightmost node in current.left (predecessor).
If predecessor.right == null:
Set predecessor.right = current (thread).
Move current = current.left.
Else (thread already set, second time visit):
Set predecessor.right = null (remove thread).
Visit current.
Move current = current.right.
This matches standard Morris inorder traversal.
Pseudo-code (Recursive Inorder, O(h) Space):
Complexity Analysis:
Let n be the number of nodes.
Time Complexity:
Inorder traversal touches each node once → O(n).
Space Complexity:
Recursive approach: O(h) (call stack), worst-case O(n); best balanced O(logn).
Morris traversal (follow-up): O(1) additional space (no stack).
5. Java code
6. C code
7. C++ code
8. Python code
9. JavaScript code
Comments
Post a Comment