Leetcode 99 — Recover Binary Search Tree — Constant space

Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure with constant space.

Example 1:

Input: [1,3,null,null,2]    
   1   
 /  
3   
 \    
  2 
Output: [3,1,null,null,2]    
  3   
 /  
1   
 \    
  2

Example 2:

Input: [3,1,4,null,null,2]   
  3  
 / \ 
1   4    
   /   
  2 
Output: [2,1,4,null,null,3]   
  2  
 / \ 
1   4    
   /   
  3

A solution using O(n) space is pretty straight forward using stack. but we need to achieve it with constant space.

Also we know that in-order traversal of BST is sorted output. So while doing in-order traversal, we should find 2 nodes, which need to be swapped to get the sorted output.

With Morris Traversal, we can achieve in-order traversal with constant memory

https://gist.github.com/sudipp

Leetcode 99 - Recover Binary Search Tree - Constant space