> For the complete documentation index, see [llms.txt](https://ucan.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ucan.gitbook.io/notes/tree/99.-recover-binary-search-tree.md).

# 99. Recover Binary Search Tree!

```java

class Solution {
    TreeNode first = null;
    TreeNode second = null;

    TreeNode prev = null;
    
    public void recoverTree(TreeNode root) {
        // The first element is always larger than its next one, while the second element is always smaller than its previous one.
        // The recursive call will use a O(logN) space.
        inorder(root);
        int temp = first.val;
        first.val=second.val;
        second.val = temp;
    }
    
    private void inorder(TreeNode node){
        if(node==null) return;
        
        inorder(node.left);
        if(prev!=null && prev.val>=node.val){
            if (first == null){
                first = prev;
            }
            second = node;
        }
        prev = node;
        inorder(node.right);
    }
}
```