> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1-100/recover-binary-search-tree.md).

# 99. Recover Binary Search Tree

### Description

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

### Constraints

### Approach

### Links

* [GeeksforGeeks](https://www.geeksforgeeks.org/fix-two-swapped-nodes-of-bst/)
* [Leetcode](https://leetcode.com/problems/recover-binary-search-tree/)
* [ProgramCreek](https://www.programcreek.com/2014/05/leetcode-recover-binary-search-tree-java/)
* [YouTube](https://youtu.be/LR3K5XAWV5k)

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** \[1, 3, null, null, 2]

<div align="left"><img src="/files/-MFg1T3-UGTLi7bsK-li" alt=""></div>

**Output:** \[3, 1, null, null, 2]

<div align="left"><img src="/files/-MFg1aBVm4s16O7WeJT4" alt=""></div>
{% endtab %}

{% tab title="Example 2" %}
Input: \[3, 1, 4, null, null, 2]

<div align="left"><img src="/files/-MFg23pPtSbSoKFbxie5" alt=""></div>

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

<div align="left"><img src="/files/-MFg2MdbGWtXNERT9kaH" alt=""></div>
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="TreeNode" %}

```java
// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}
    
    TreeNode(int val) { this.val = val; }
    
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
```

{% endtab %}

{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(1) in the best case, and O(N) in the worst case when 
 *    one of the swapped nodes is a rightmost leaf.
 * Space complexity : up to O(H) to keep the recursion stack, 
 *    where H is a tree height.
 */

class Solution {
    private TreeNode first, last, prev;
    
    public void recoverTree(TreeNode root) {
        if(root == null) return;

        findFaultyNodes(root);
        
        if(first != null && last != null) {
            int val = first.val;
            first.val = last.val;
            last.val = val;
        }
    }
    
    // Basically inorder traversal
    private void findFaultyNodes(TreeNode root) {
        if(root == null) return;
        
        findFaultyNodes(root.left);
        
        if(prev == null) {
            prev = root;
        } else {
            if(prev.val > root.val) {
                if(first == null) {
                    first = prev;
                }
                last = root;
            }
            prev = root;
        }
        
        findFaultyNodes(root.right);
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(1) in the best case, and O(N) in the worst case when 
 *    one of the swapped nodes is a rightmost leaf.
 * Space complexity : up to O(H) to keep the recursion stack, 
 *    where H is a tree height.
 */
 
 class Solution {  
    public void recoverTree(TreeNode root) {
        if(root == null) return;
        
        TreeNode first = null, last = null, prev = null;
        Deque<TreeNode> stack = new ArrayDeque();
        
        while(!stack.isEmpty() || root != null) {
            while(root != null) {
                stack.add(root);
                root = root.left;
            }
            root = stack.removeLast();

            if(prev != null && prev.val > root.val) {
                last = root;
                if(first == null) {
                    first = prev;
                } else {
                    break;
                }
            }
            
            prev = root;
            root = root.right;
        }
        
        if(first != null && last != null) {
            int val = first.val;
            first.val = last.val;
            last.val = val;
        }
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

* A solution using O(*n*) space is pretty straight forward.
* Could you devise a constant space solution?