Recover Binary Search Tree
Two nodes of a BST are swapped by mistake. Recover the tree without changing its structure.

30:00

Recover Binary Search Tree
medium
Topics
Companies

Two nodes of a BST are 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]
Constraints:

  • The number of nodes is in the range [2,1000][2, 1000].

  • −231≤Node.val≤231−1-2^{31} \leq \text{Node.val} \leq 2^{31} - 1

  • Exactly two nodes' values are swapped by mistake.

Input
arr ={"root":[1,3,null,null,2]}

Initialize first, second, prev to null. Start in-order traversal.

Phase

traversing

1

3

2

Current Node
Previous Node
Swapped Nodes
Visited
Variables
No variables to display
DepthFunction Call
Stack empty
0/23