Skip to main content
Back to ChallengesRecover Binary Search TreeHard 50 min

Recover Binary Search Tree

You are given the root of a binary search tree (BST), where the values of **exactly two nodes** have been swapped by mistake.

Recover the tree without changing its structure. Return the inorder traversal after recovery.

Examples

Input: root = [1,3,null,null,2]
Output: [1,2,3]
3 and 2 were swapped. After recovery: [3,1,null,null,2] → inorder [1,2,3].
Input: root = [3,1,4,null,null,2]
Output: [1,2,3,4]
3 and 2 were swapped. Recovered inorder.

Constraints

  • • Number of nodes in [2, 1000]
  • • -2^31 <= Node.val <= 2^31 - 1

Complexity Analysis

Time
O(n) for standard inorder; O(1) extra space with Morris traversal.
Space
O(h) with recursion, O(1) with Morris.

Test Cases

#1 Adjacent swap
Input: [1,3,null,null,2]
Expected: [1,2,3]
#2 Non-adjacent swap
Input: [3,1,4,null,null,2]
Expected: [1,2,3,4]
JavaScript
Output
Click "Run Code" to see output here...