This page explains Java solution to problem `Recover Binary Search Tree`

using `In Order Traversal of Tree `

data structure.

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

Recover the tree without changing its structure.

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

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

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

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

```
package com.vc.hard;
/**
* 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 RecoverBinarySearchTree {
private TreeNode prev = null, small = null, large = null;
public void recoverTree(TreeNode root) {
helper(root);
int temp = small.val;
small.val = large.val;
large.val = temp;
}
private void helper(TreeNode root) {
if(root != null) {
helper(root.left);
if(prev != null && prev.val > root.val) {
if(large == null) large = prev;
small = root;
}
prev = root;
helper(root.right);
}
}
}
```

O(N) Where

N is total number of elements in an input Tree

O(1)