package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;
/**Two elements of a binary search tree (BST) are swapped by mistake.

 Recover the tree without changing its structure.

 Note:
 A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?*/
public class _99 {
	TreeNode firstElement = null;
	TreeNode secondElement = null;

	TreeNode prevElement = new TreeNode(Integer.MIN_VALUE);

	public void recoverTree(TreeNode root) {
		traverseTree(root);

		//swap the two elements
		int temp = firstElement.val;
		firstElement.val = secondElement.val;
		secondElement.val = temp;
	}

	private void traverseTree(TreeNode root) {
		if (root == null) {
			return;
		}

		traverseTree(root.left);

		//prevElement means the one previous to the current root, refer to in-order traversal, previous element must be smaller than the current root
		//if it's bigger, then we find the first element, thus we store it in the variable called firstElement
		if (firstElement == null && prevElement.val >= root.val) {
			firstElement = prevElement;
		}

		if (firstElement != null && prevElement.val >= root.val) {
			secondElement = root;
		}

		//this is the last step in the "do some business logic", so we'll always to have update the previous node to be the current root before it traverses the right subtree
		//since the current root will be the new previous node for the right subtree.
		prevElement = root;

		traverseTree(root.right);
	}

}
@@ -80,16 +80,57 @@
 ode;%0A/**
+%0A * 99. Recover Binary Search Tree%0A *%0A * 
 Two elem
@@ -188,17 +188,18 @@
 istake.%0A
-%0A
+ *
  Recover
@@ -352,11 +352,14 @@
 ion?
+%0A 
 */%0A
+%0A
 publ
@@ -373,17 +373,54 @@
 s _99 %7B%0A
-%09
+  public static class Solution1 %7B%0A    
 TreeNode
@@ -441,17 +441,20 @@
 = null;%0A
-%09
+    
 TreeNode
@@ -477,17 +477,20 @@
  null;%0A%0A
-%09
+    
 TreeNode
@@ -538,17 +538,20 @@
 ALUE);%0A%0A
-%09
+    
 public v
@@ -583,18 +583,22 @@
 root) %7B%0A
-%09%09
+      
 traverse
@@ -610,18 +610,22 @@
 root);%0A%0A
-%09%09
+      
 //swap t
@@ -640,18 +640,22 @@
 lements%0A
-%09%09
+      
 int temp
@@ -675,18 +675,22 @@
 nt.val;%0A
-%09%09
+      
 firstEle
@@ -719,18 +719,22 @@
 nt.val;%0A
-%09%09
+      
 secondEl
@@ -751,21 +751,27 @@
 = temp;%0A
-%09%7D%0A%0A%09
+    %7D%0A%0A    
 private 
@@ -805,18 +805,22 @@
 root) %7B%0A
-%09%09
+      
 if (root
@@ -835,26 +835,39 @@
 ) %7B%0A
-%09%09%09return;%0A%09%09%7D%0A%0A%09%09
+        return;%0A      %7D%0A%0A      
 trav
@@ -888,18 +888,22 @@
 left);%0A%0A
-%09%09
+      
 //prevEl
@@ -1036,18 +1036,22 @@
 nt root%0A
-%09%09
+      
 //if it'
@@ -1145,18 +1145,22 @@
 Element%0A
-%09%09
+      
 if (firs
@@ -1210,19 +1210,24 @@
 .val) %7B%0A
-%09%09%09
+        
 firstEle
@@ -1246,23 +1246,31 @@
 lement;%0A
-%09%09%7D%0A%0A%09%09
+      %7D%0A%0A      
 if (firs
@@ -1324,11 +1324,16 @@
 ) %7B%0A
-%09%09%09
+        
 seco
@@ -1354,15 +1354,23 @@
 ot;%0A
-%09%09%7D%0A%0A%09%09
+      %7D%0A%0A      
 //th
@@ -1532,18 +1532,22 @@
 subtree%0A
-%09%09
+      
 //since 
@@ -1616,18 +1616,22 @@
 ubtree.%0A
-%09%09
+      
 prevElem
@@ -1647,10 +1647,14 @@
 t;%0A%0A
-%09%09
+      
 trav
@@ -1679,9 +1679,17 @@
 t);%0A
-%09%7D%0A%0A%7D
+    %7D%0A%0A  %7D%0A%7D%0A

refactor 99