[Leetcode] Recover Binary Search Tree

Problem

Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure.
Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Algorithm

In-order traversal of a BST yields a sorted array. If two nodes are swapped, one of them will be a "peak", and another will be a valley in the array. For example, A = [1,2,3,4]. Swapping 1 and 3 yields [3,2,1,4], then 3 becomes a peak, and 1 becomes a valley. 

If O(n) space is allowed, we can print the in-order traversed array, then identify the peak and valley. Since the constant space is required,  two pointers are needed to store the swapped nodes, while we do an in-order traversal of the BST.

I used three pointers, l, m and r, to identify the peak and valley node. If m.val is smaller than both l.val and r.val, it is a valley. In order to simplify the boundary condition, we can initialize the l.val and m.val = Integer.min_value. Also, if we push a Integer.max_value into the stack, the last node can be easily handled.

Actually, the space complexity is O(log(n)), since we used a stack to store the nodes.
See
Inorder Tree Traversal without recursion and without stack!

Code