Data Structures19 sections · 729 units
Open in Course

Problem - Recover BST

Fix swapped nodes

Two nodes of a BST were swapped by mistake. Recover the tree without changing its structure. Example: In [1,3,null,null,2][1,3,null,null,2], nodes 11 and 33 were swapped.

Correct tree is [3,1,null,null,2][3,1,null,null,2]. The BST property is violated at two positions. You need to identify which two nodes were swapped and fix them.

Follow-up: Can you solve it using O(1)O(1) space (excluding recursion stack)? Constraints: up to 10001000 nodes.