DiffPush Tier Binary Search Trees · Practice Problems O(n) · O(h)
Overnight, exactly two bins in a size-sorted storage tree were swapped by a forklift mix-up. The floor plan is intact — only the size labels on those two bins are wrong. A checker walks the shelves in sorted order, flags the first and last spots where the rising sequence dips, and re-prints those two labels to restore perfect order without touching a single shelf.
Input: A binary search tree as a level-order array (null marks a missing child) in which exactly two node values have been swapped.
Output: Return the repaired tree serialized as a level-order array with trailing nulls trimmed — structure unchanged, the two swapped values restored.
2 <= number of nodes <= 10^5-2^31 <= node value <= 2^31 - 1Exactly two values are out of place; a solution existsFollow-up: O(1) extra space is possible with Morris traversalInput: {"tree":[1,3,null,null,2]}
Output: [3,1,null,null,2]
The inorder walk 3, 1, 2 dips once; swapping 3 and 1 restores the BST.
Input: {"tree":[3,1,4,null,null,2]}
Output: [2,1,4,null,null,3]
The walk 1, 3, 2, 4 dips at 3→2; swapping 3 and 2 repairs the order.