# Recover Binary Search Tree

This page explains Java solution to problem `Recover Binary Search Tree` using `In Order Traversal of Tree `data structure.

## Problem Statement

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

Recover the tree without changing its structure.

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

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
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);
}
}
}
``````

## Time Complexity

O(N) Where
N is total number of elements in an input Tree

O(1)