# Recover Binary Search Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/recover-binary-search-tree)
Canonical: https://scaleengineer.com/dsa/problems/recover-binary-search-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree, Binary Search Tree
**Companies:** [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Microsoft](https://scaleengineer.com/companies/microsoft), [TikTok](https://scaleengineer.com/companies/tiktok), [Yahoo](https://scaleengineer.com/companies/yahoo)
---
## Problem
You are given the `root` of a binary search tree (BST), where the values of **exactly** two nodes of the tree were swapped by mistake. _Recover the tree without changing its structure_.

**Example 1:**

![](https://assets.glich.co/dsa/recover-binary-search-tree/image0.jpg) 

**Input:** root = [1,3,null,null,2]
**Output:** [3,1,null,null,2]
**Explanation:** 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

**Example 2:**

![](https://assets.glich.co/dsa/recover-binary-search-tree/image1.jpg) 

**Input:** root = [3,1,4,null,null,2]
**Output:** [2,1,4,null,null,3]
**Explanation:** 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

**Constraints:**

* The number of nodes in the tree is in the range `[2, 1000]`.
* `-231 <= Node.val <= 231 - 1`

**Follow up:** A solution using `O(n)` space is pretty straight-forward. Could you devise a constant `O(1)` space solution?

# Approaches
## In-order Traversal and Sort
A straightforward but less efficient approach is to perform an in-order traversal of the tree, store all the node values in a list, sort the list to get the correct order, and then iterate through the tree again (or a list of nodes from the first traversal) to update the node values with the sorted ones.
**Time:** O(N log N) · **Space:** O(N)
**Pros:** Conceptually simple and easy to understand.; Easy to implement correctly.
**Cons:** Has a suboptimal time complexity of O(N log N) due to sorting.; Uses O(N) extra space, which can be inefficient for very large trees.; It reassigns values to all nodes, which is unnecessary as only two nodes are incorrect.
### Explanation
This method relies on the fundamental property of a BST: an in-order traversal yields sorted values. By capturing the node references and their values, we can correct the tree by sorting the values and reassigning them to the nodes in their correct in-order positions.

```java
public void recoverTree(TreeNode root) {
    List<TreeNode> nodes = new ArrayList<>();
    List<Integer> vals = new ArrayList<>();
    inorderTraversal(root, nodes, vals);
    Collections.sort(vals);
    for (int i = 0; i < nodes.size(); i++) {
        nodes.get(i).val = vals.get(i);
    }
}

private void inorderTraversal(TreeNode node, List<TreeNode> nodes, List<Integer> vals) {
    if (node == null) {
        return;
    }
    inorderTraversal(node.left, nodes, vals);
    nodes.add(node);
    vals.add(node.val);
    inorderTraversal(node.right, nodes, vals);
}
```
### Algorithm
- Create two lists: one to store `TreeNode` objects (`nodes`) and another for their values (`vals`).
- Perform an in-order traversal of the BST. In the traversal, add each visited node to the `nodes` list and its value to the `vals` list.
- After the traversal, the `nodes` list contains all nodes in in-order sequence, but the `vals` list is out of order due to the swap.
- Sort the `vals` list. This gives the correct sequence of values for a valid BST.
- Iterate from `i = 0` to `n-1`, where `n` is the number of nodes. For each `i`, update the value of the node at `nodes.get(i)` with the value from the sorted list `vals.get(i)`. This restores the BST property.

## Find Misplaced Nodes using O(N) Space
This approach improves upon the first by avoiding the O(N log N) sort. We can identify the two swapped nodes by finding the discrepancies in the in-order traversal sequence in a single linear scan. This brings the time complexity down to O(N).
**Time:** O(N) · **Space:** O(N)
**Pros:** Achieves optimal time complexity of O(N).; Directly finds and swaps only the two incorrect nodes.
**Cons:** Uses O(N) extra space to store the node references, which can be significant for a large tree.
### Explanation
An in-order traversal of a valid BST yields a sorted list of values. If exactly two nodes are swapped, this sorted property is violated at one or two places. We can find these violations to identify the swapped nodes.

- If the swapped nodes are adjacent in the in-order sequence (e.g., `[1, 3, 2, 4]`), there will be one violation. The two nodes involved (`3` and `2`) are the ones to swap.
- If the swapped nodes are not adjacent (e.g., `[1, 5, 3, 4, 2, 6]`), there will be two violations. The first node of the first violation (`5`) and the second node of the second violation (`2`) are the ones to swap.

This logic can be implemented by storing the in-order traversal and then scanning it.

```java
public void recoverTree(TreeNode root) {
    List<TreeNode> list = new ArrayList<>();
    inorder(root, list);
    
    TreeNode first = null;
    TreeNode second = null;
    
    for (int i = 0; i < list.size() - 1; i++) {
        if (list.get(i).val > list.get(i + 1).val) {
            second = list.get(i + 1);
            if (first == null) {
                first = list.get(i);
            } else {
                break;
            }
        }
    }
    
    int temp = first.val;
    first.val = second.val;
    second.val = temp;
}

private void inorder(TreeNode node, List<TreeNode> list) {
    if (node == null) return;
    inorder(node.left, list);
    list.add(node);
    inorder(node.right, list);
}
```
### Algorithm
- Perform an in-order traversal and store all the `TreeNode` objects in a list, say `inorderNodes`.
- Initialize two `TreeNode` pointers, `first` and `second`, to `null`. These will store the two nodes that need to be swapped.
- Iterate through the `inorderNodes` list from the beginning. Look for a point `i` where `inorderNodes.get(i).val > inorderNodes.get(i+1).val`.
- When the first such violation is found, set `first = inorderNodes.get(i)` and `second = inorderNodes.get(i+1)`.
- If a second violation is found, update `second` to be the second node of that violation, which is `inorderNodes.get(i+1)`.
- After the loop, swap the values of the `first` and `second` nodes.

## Recursive In-order Traversal with O(H) Space
We can optimize the space complexity by not storing the entire traversal in a list. Instead, we can find the two misplaced nodes during a single recursive in-order traversal, using pointers to keep track of the previously visited node and the nodes to be swapped.
**Time:** O(N) · **Space:** O(H)
**Pros:** More space-efficient than the list-based approach, especially for balanced trees (O(log N) space).; Maintains O(N) time complexity.
**Cons:** The space complexity is dependent on the height of the tree, which can be O(N) in the worst case for a skewed tree.
### Explanation
This approach avoids creating an explicit list of nodes. It uses the same logic of finding violations in the in-order sequence but does it on the fly during the recursion. The recursion stack itself provides the memory to keep track of the traversal path, leading to O(H) space complexity, where H is the height of the tree.

```java
class Solution {
    TreeNode first = null;
    TreeNode second = null;
    TreeNode prev = null;

    public void recoverTree(TreeNode root) {
        inorder(root);
        
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }

    private void inorder(TreeNode current) {
        if (current == null) {
            return;
        }
        inorder(current.left);

        if (prev != null && prev.val > current.val) {
            if (first == null) {
                first = prev;
            }
            second = current;
        }
        prev = current;

        inorder(current.right);
    }
}
```
### Algorithm
- Initialize three `TreeNode` pointers: `first = null`, `second = null`, and `prev = null`. `prev` will keep track of the previously visited node in the in-order traversal.
- Perform a recursive in-order traversal starting from the root.
- Inside the traversal, after visiting the left subtree (but before the right), compare the current node's value with the `prev` node's value.
- If `prev != null` and `prev.val > current.val`, a violation is found.
  - If `first` is `null`, it's the first violation. Set `first = prev`.
  - In any violation, the second misplaced node candidate is the current node, so always set `second = current`.
- After processing the current node, update `prev = current` before moving to the right subtree.
- After the traversal, swap the values of `first` and `second`.

## Morris In-order Traversal with O(1) Space
To achieve the optimal constant space complexity as requested in the follow-up, we can use Morris In-order Traversal. This advanced technique allows traversing the tree without using recursion or an explicit stack by temporarily modifying the tree structure with 'threads' which are then removed to restore the original structure.
**Time:** O(N) · **Space:** O(1)
**Pros:** Optimal O(1) space complexity.; Optimal O(N) time complexity.
**Cons:** The logic is significantly more complex to understand and implement compared to other approaches.; It temporarily modifies the tree structure, which might be an issue in a multi-threaded environment without proper locking.
### Explanation
Morris Traversal is a clever way to implement in-order traversal with O(1) space. It works by finding the in-order predecessor of the current node. If the predecessor's right child is null, we create a temporary link (thread) from it to the current node and move to the current node's left child. If the predecessor's right child already points to the current node, it means we have finished visiting the left subtree, so we break the thread, visit the current node, and move to its right child. We embed our violation-checking logic into the 'visit' step of this traversal.

```java
public void recoverTree(TreeNode root) {
    TreeNode first = null, second = null, prev = null;
    TreeNode current = root;

    while (current != null) {
        if (current.left == null) {
            // Visit current node
            if (prev != null && prev.val > current.val) {
                if (first == null) first = prev;
                second = current;
            }
            prev = current;
            current = current.right;
        } else {
            TreeNode predecessor = current.left;
            while (predecessor.right != null && predecessor.right != current) {
                predecessor = predecessor.right;
            }

            if (predecessor.right == null) {
                predecessor.right = current; // Create thread
                current = current.left;
            } else {
                predecessor.right = null; // Remove thread
                // Visit current node
                if (prev != null && prev.val > current.val) {
                    if (first == null) first = prev;
                    second = current;
                }
                prev = current;
                current = current.right;
            }
        }
    }
    
    // Swap the values
    int temp = first.val;
    first.val = second.val;
    second.val = temp;
}
```
### Algorithm
- Initialize pointers: `first = null`, `second = null`, `prev = null`, and `current = root`.
- Use the Morris Traversal algorithm to iterate through the tree in an in-order fashion without recursion or a stack.
- The core of Morris Traversal involves creating temporary 'threaded' links from a node's in-order predecessor back to the node itself.
- In the steps where a node would be 'visited' in a standard in-order traversal, apply the same logic as in the recursive approach:
  - Compare `prev.val` with `current.val`.
  - If `prev != null` and `prev.val > current.val`, update `first` and `second` pointers accordingly.
  - Update `prev = current`.
- The Morris Traversal algorithm ensures that the tree's original structure is restored after the traversal is complete.
- After the traversal loop finishes, swap the values of the nodes pointed to by `first` and `second`.

# Solutions
### CSharp

```csharp
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { private TreeNode prev , first , second ; public void RecoverTree ( TreeNode root ) { dfs ( root ); int t = first . val ; first . val = second . val ; second . val = t ; } private void dfs ( TreeNode root ) { if ( root == null ) { return ; } dfs ( root . left ); if ( prev != null && prev . val > root . val ) { if ( first == null ) { first = prev ; } second = root ; } prev = root ; dfs ( root . right ); } }
```

### Java

```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; * } * } */ class Solution { private TreeNode prev ; private TreeNode first ; private TreeNode second ; public void recoverTree ( TreeNode root ) { dfs ( root ); int t = first . val ; first . val = second . val ; second . val = t ; } private void dfs ( TreeNode root ) { if ( root == null ) { return ; } dfs ( root . left ); if ( prev != null && prev . val > root . val ) { if ( first == null ) { first = prev ; } second = root ; } prev = root ; dfs ( root . right ); } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {void} Do not return anything, modify root in-place instead. */ var recoverTree =
  function (root) {
    let prev = null;
    let first = null;
    let second = null;
    function dfs(root) {
      if (!root) {
        return;
      }
      dfs(root.left);
      if (prev && prev.val > root.val) {
        if (!first) {
          first = prev;
        }
        second = root;
      }
      prev = root;
      dfs(root.right);
    }
    dfs(root);
    const t = first.val;
    first.val = second.val;
    second.val = t;
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: void recoverTree ( TreeNode * root ) { TreeNode * prev = nullptr ; TreeNode * first = nullptr ; TreeNode * second = nullptr ; function < void ( TreeNode * root ) > dfs = [ & ]( TreeNode * root ) { if ( ! root ) return ; dfs ( root -> left ); if ( prev && prev -> val > root -> val ) { if ( ! first ) first = prev ; second = root ; } prev = root ; dfs ( root -> right ); }; dfs ( root ); swap ( first -> val , second -> val ); } };
```

### Python

```python
''' Without nonlocal, any assignment to prev, first, and second inside dfs would be treated as creating new local variables within dfs, rather than modifying the outer variables. ''' # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def recoverTree ( self , root : Optional [ TreeNode ]) -> None : """ Do not return anything, modify root in-place instead. """ def dfs ( root ): if root is None : return nonlocal prev , first , second dfs ( root . left ) if prev and prev . val > root . val : if first is None : first = prev second = root prev = root dfs ( root . right ) prev = first = second = None dfs ( root ) first . val , second . val = second . val , first . val
```