Two of the nodes of a Binary Search Tree (BST) are swapped. Fix (or correct) the BST by swapping them back. Do not change the structure of the tree.
Note: It is guaranteed that the given input will form BST, except for 2 nodes that will be wrong.
 
Example 1:
Input:
       10
     /    \
    5      8
   / \
  2   20
Output: 1
Explanation:
 
Example 2:
Input:
         11
       /    \
      3      17
       \    /
        4  10
Output: 1 
Explanation: 
By swapping nodes 11 and 10, the BST 
can be fixed.
Your Task:
You don't need to take any input. Just complete the function correctBst() that takes root node as parameter. The function should return the root of corrected BST. BST will then be checked by driver code and 0 or 1 will be printed.
Expected Time Complexity: O(Number of nodes)
Expected Auxiliary Space: O(logN), N = number of nodes
 
Constraints:
1 <= Number of nodes <= 10^5

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Data structures

Range queries

Starter code: #User function Template for python3



'''

# Tree Node

class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None

        

'''



class Solution:

    def correctBST(self, root):

        # code here

Solutions:
import sys
from collections import deque

class Solution:

	def correctBST(self, root):
		mid = first = last = None
		prev = None

		def inorder(root):
			if root is None:
				return
			inorder(root.left)
			nonlocal mid, first, last, prev
			if prev != None and root.data < prev.data:
				if first == None:
					first = prev
					mid = root
				else:
					last = root
			prev = root
			inorder(root.right)
		inorder(root)
		if first != None and last != None:
			(first.data, last.data) = (last.data, first.data)
		else:
			(first.data, mid.data) = (mid.data, first.data)
		return root


class Solution:

	def __init__(self):
		self.first = None
		self.last = None
		self.prev = None

	def swap(self, prev, curr):
		tmp = prev.data
		prev.data = curr.data
		curr.data = tmp

	def rec(self, root):
		if root is not None:
			self.rec(root.left)
			if self.prev is not None and self.prev.data > root.data:
				if self.first is None:
					self.first = self.prev
					self.last = root
				else:
					self.last = root
			self.prev = root
			self.rec(root.right)

	def correctBST(self, root):
		self.rec(root)
		if self.first is not None and self.last is not None:
			self.swap(self.first, self.last)
		return root


class Solution:

	def getBSTNode(self, root, arr):
		if root == None:
			return
		self.getBSTNode(root.left, arr)
		arr.append(root.data)
		self.getBSTNode(root.right, arr)

	def updateBST(self, node, arr):
		if node == None:
			return
		self.updateBST(node.left, arr)
		node.data = arr.pop(len(arr) - 1)
		self.updateBST(node.right, arr)

	def correctBST(self, root):
		arr = []
		self.getBSTNode(root, arr)
		arr = sorted(arr, reverse=True)
		self.updateBST(root, arr)
		return root


import sys

class Solution:

	def correctBST(self, root):

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			if prev[0] != None and root.data < prev[0].data:
				if first[0] == None:
					first[0] = prev[0]
					middle[0] = root
				else:
					last[0] = root
			prev[0] = root
			inorder(root.right)
		first = [None]
		last = [None]
		middle = [None]
		prev = [None]
		inorder(root)
		if first[0] != None and last[0] != None:
			(first[0].data, last[0].data) = (last[0].data, first[0].data)
		elif first[0] != None and middle[0] != None:
			(first[0].data, middle[0].data) = (middle[0].data, first[0].data)
		return root


class Solution:

	def correctBST(self, root):

		def _solve(nd):
			if not nd:
				return
			nonlocal first, prev
			if _solve(nd.left):
				return True
			if not first:
				if prev and prev.data > nd.data:
					first = prev
			elif first.data < nd.data:
				(first.data, prev.data) = (prev.data, first.data)
				return True
			prev = nd
			if _solve(nd.right):
				return True
			return False
		(first, prev) = (None, None)
		if not _solve(root):
			(first.data, prev.data) = (prev.data, first.data)
		return root


class Solution:

	def correctBST(self, root):
		mid = first = last = None
		prev = None

		def inorder(root):
			if root is None:
				return
			inorder(root.left)
			nonlocal mid, first, last, prev
			if prev != None and root.data < prev.data:
				if first == None:
					first = prev
					mid = root
				else:
					last = root
			prev = root
			inorder(root.right)
		inorder(root)
		if first != None and last != None:
			(first.data, last.data) = (last.data, first.data)
		else:
			(first.data, mid.data) = (mid.data, first.data)
		return root


class Solution:

	def __init__(self):
		self.first = None
		self.middle = None
		self.second = None

	def check(self, prev, curr):
		if prev and prev.data > curr.data:
			if self.first == None:
				self.first = prev
				self.middle = curr
			elif self.second == None:
				self.second = curr

	def correctBST(self, root):
		root1 = root
		prev = None
		curr = root
		while curr:
			node = curr.left
			if node == None:
				self.check(prev, curr)
				prev = curr
				curr = curr.right
			else:
				while node.right and node.right != curr:
					node = node.right
				if node.right == None:
					node.right = curr
					curr = curr.left
				else:
					node.right = None
					self.check(prev, curr)
					prev = curr
					curr = curr.right
		if self.first and self.second:
			temp = self.first.data
			self.first.data = self.second.data
			self.second.data = temp
		else:
			temp = self.first.data
			self.first.data = self.middle.data
			self.middle.data = temp
		return root1


class Solution:

	def correctBST(self, root):
		elements = []
		index = [0]

		def getEle(node):
			if node is None:
				return
			getEle(node.left)
			elements.append(node.data)
			getEle(node.right)
		temp = root
		getEle(temp)
		elements.sort()

		def setEle(node):
			if node is None:
				return
			setEle(node.left)
			node.data = elements[index[0]]
			index[0] += 1
			setEle(node.right)
		temp = root
		setEle(temp)
		return root


class Solution:

	def correctBST(self, root):
		self.first = None
		self.second = None
		self.prev = None

		def inorder(node=root):
			if not node:
				return False
			if inorder(node.left):
				return True
			if self.prev:
				if node.data < self.prev.data and (not self.first):
					self.first = self.prev
					self.second = node
				elif node.data < self.prev.data and self.first:
					self.second = node
					return True
			self.prev = node
			if inorder(node.right):
				return True
		inorder()
		t = self.first.data
		self.first.data = self.second.data
		self.second.data = t
		return root


class Solution:

	def correctBSTUtil(self, root, first, middle, last, prev):
		if root:
			self.correctBSTUtil(root.left, first, middle, last, prev)
			if prev[0] and root.data < prev[0].data:
				if not first[0]:
					first[0] = prev[0]
					middle[0] = root
				else:
					last[0] = root
			prev[0] = root
			self.correctBSTUtil(root.right, first, middle, last, prev)

	def correctBST(self, root):
		first = [None]
		middle = [None]
		last = [None]
		prev = [None]
		self.correctBSTUtil(root, first, middle, last, prev)
		if first[0] and last[0]:
			(first[0].data, last[0].data) = (last[0].data, first[0].data)
		elif first[0] and middle[0]:
			(first[0].data, middle[0].data) = (middle[0].data, first[0].data)
		return root


import sys

class Solution:

	def correctBST(self, root):

		def inorder(root):
			if not root:
				return
			inorder(root.left)
			arr.append(root.data)
			inorder(root.right)

		def update(node, arr):
			if not node:
				return
			update(node.left, arr)
			node.data = arr.pop(len(arr) - 1)
			update(node.right, arr)
		arr = []
		inorder(root)
		arr = sorted(arr, reverse=True)
		update(root, arr)
		return root


class Solution:

	def correctBST(self, root):

		def find_wrong(root):
			nonlocal x, y, prev
			if root is None:
				return
			find_wrong(root.left)
			if prev and root.data < prev.data:
				y = root
				if x is None:
					x = prev
				else:
					return
			prev = root
			find_wrong(root.right)
		x = y = prev = None
		find_wrong(root)
		(x.data, y.data) = (y.data, x.data)
		return root


class Solution:

	def correctBST(self, root):
		self.inorder = []
		self.inOrder(root)
		the_two = []
		for i in range(len(self.inorder) - 1):
			if self.inorder[i].data > self.inorder[i + 1].data:
				the_two.append(i)
		if len(the_two) == 1:
			(f, s) = (self.inorder[the_two[0]], self.inorder[the_two[0] + 1])
			(f.data, s.data) = (s.data, f.data)
		else:
			(f, s) = (self.inorder[the_two[0]], self.inorder[the_two[1] + 1])
			(f.data, s.data) = (s.data, f.data)
		return root

	def inOrder(self, r):
		if r:
			self.inOrder(r.left)
			self.inorder.append(r)
			self.inOrder(r.right)


class Solution:

	def correctBST(self, root):
		self.f = None
		self.m = None
		self.l = None
		self.prev = None
		self.inorder(root)
		if root == self.f:
			root = self.f
		if self.l == None:
			(self.f.data, self.m.data) = (self.m.data, self.f.data)
		else:
			(self.f.data, self.l.data) = (self.l.data, self.f.data)
		return root

	def inorder(self, root):
		if not root:
			return
		self.inorder(root.left)
		if self.prev and root.data < self.prev.data:
			if self.f == None:
				self.f = self.prev
				self.m = root
			else:
				self.l = root
		self.prev = root
		self.inorder(root.right)


class Solution:

	def correctBST(self, root):
		l = []
		global prev
		prev = [-2 ** 31 - 2, -2 ** 31 - 2]

		def fun(node):
			global prev
			if node is None:
				return
			fun(node.left)
			if node.data < prev[0] and (not l):
				l.append(prev[1])
				l.append(node)
				f = 1
			elif node.data < prev[0] and l:
				l.pop()
				l.append(node)
			prev = [node.data, node]
			fun(node.right)
		fun(root)
		(l[0].data, l[1].data) = (l[1].data, l[0].data)
		return root


class Solution:

	def correctBST(self, root):
		self.first = None
		self.second = None
		self.prev = None
		self.inorder(root)
		(self.first.data, self.second.data) = (self.second.data, self.first.data)
		return root

	def inorder(self, node):
		if node.left:
			self.inorder(node.left)
		if self.prev and node.data < self.prev.data:
			if self.first == None:
				self.first = self.prev
				self.second = node
			else:
				self.second = node
		self.prev = node
		if node.right:
			self.inorder(node.right)


class Solution:

	def inorder(self, root, prev, first, second):
		if root.left != None:
			(prev, first, second) = self.inorder(root.left, prev, first, second)
		if prev != None:
			if prev.data > root.data:
				if first == None:
					first = prev
				second = root
		prev = root
		if root.right != None:
			(prev, first, second) = self.inorder(root.right, prev, first, second)
		return (prev, first, second)

	def correctBST(self, root):
		(prev, first, second) = self.inorder(root, prev=None, first=None, second=None)
		(first.data, second.data) = (second.data, first.data)
		return root


def inOrderRead(root, arr, nodes):
	if root == None:
		return
	if root.left:
		inOrderRead(root.left, arr, nodes)
	arr.append(root.data)
	nodes.append(root)
	if root.right:
		inOrderRead(root.right, arr, nodes)

class Solution:

	def correctBST(self, root):
		badNodeL = None
		badNodeR = None
		arr = []
		nodes = []
		inOrderRead(root, arr, nodes)
		if arr[0] != min(arr):
			badNodeL = nodes[0]
		if arr[-1] != max(arr):
			badNodeR = nodes[-1]
		for n in range(1, len(arr) - 1):
			if not badNodeL:
				if arr[n] > arr[n + 1]:
					badNodeL = nodes[n]
		for n in range(len(arr) - 1, 0, -1):
			if not badNodeR:
				if arr[n] < arr[n - 1]:
					badNodeR = nodes[n]
		temp = badNodeR.data
		badNodeR.data = badNodeL.data
		badNodeL.data = temp
		return root


from collections import deque

class Solution:

	def __init__(self):
		self.ar = []

	def dfs(self, node):
		if not node:
			return
		self.dfs(node.left)
		self.ar.append((node.data, node))
		self.dfs(node.right)
		return

	def correctBST(self, root):
		incrct = []
		self.dfs(root)
		f0 = fn = False
		ars = self.ar.copy()
		ars.sort()
		p1 = 0
		p2 = 0
		while p2 < len(ars):
			if self.ar[p1] != ars[p2]:
				incrct.append(self.ar[p1][1])
				if len(incrct) == 2:
					break
			p1 += 1
			p2 += 1
		(node1, node2) = incrct
		(node1.data, node2.data) = (node2.data, node1.data)
		return root


class Solution:

	def getBSTNode(self, root, arr):
		if root == None:
			return
		self.getBSTNode(root.left, arr)
		arr.append(root)
		self.getBSTNode(root.right, arr)

	def correctBST(self, root):
		arr = []
		self.getBSTNode(root, arr)
		idx1 = -1
		idx2 = -1
		for i in range(0, len(arr) - 1):
			if arr[i].data > arr[i + 1].data:
				if idx1 == -1:
					idx1 = i
				else:
					idx2 = i + 1
		if idx2 == -1:
			idx2 = idx1 + 1
		tmp = arr[idx1].data
		arr[idx1].data = arr[idx2].data
		arr[idx2].data = tmp
		return root


class Solution:

	def correctBST(self, root):
		self.prev = None
		self.first = None
		self.second = None
		self.find_swapped_nodes(root)
		self.swap_nodes(self.first, self.second)
		return root

	def find_swapped_nodes(self, root):
		if root is None:
			return
		self.find_swapped_nodes(root.left)
		if self.prev is not None and root.data < self.prev.data:
			if self.first is None:
				self.first = self.prev
			self.second = root
		self.prev = root
		self.find_swapped_nodes(root.right)

	def swap_nodes(self, node1, node2):
		temp = node1.data
		node1.data = node2.data
		node2.data = temp


class Solution:

	def insert(self, root, l):
		if root == None:
			return
		self.insert(root.left, l)
		l.append(root.data)
		self.insert(root.right, l)

	def fill(self, root, l):
		if root == None:
			return
		self.fill(root.left, l)
		root.data = l[len(l) - 1]
		l.pop()
		self.fill(root.right, l)

	def correctBST(self, root):
		l = []
		self.insert(root, l)
		l.sort()
		l.reverse()
		self.fill(root, l)
		return root


class Solution:

	def correctBST(self, root):
		global first, sec, last, prev
		prev = None
		first = None
		sec = None
		last = None

		def rec(r):
			global first, sec, last, prev
			if r:
				rec(r.left)
				if prev:
					if prev.data > r.data:
						if not sec:
							first = prev
							sec = r
						else:
							last = r
				prev = r
				rec(r.right)
		rec(root)
		if first and last:
			(first.data, last.data) = (last.data, first.data)
		else:
			(first.data, sec.data) = (sec.data, first.data)
		return root


class Solution:

	def __init__(self):
		self.ans = []
		self.d = {}

	def correctBST(self, root):
		self.inorder(root)
		temp = sorted(self.ans)
		for i in range(len(self.ans)):
			if self.ans[i] != temp[i]:
				r1 = self.d[self.ans[i]]
				r2 = self.d[temp[i]]
				x = r1.data
				r1.data = r2.data
				r2.data = x
				return root
		return root

	def inorder(self, root):
		if root is None:
			return
		self.d[root.data] = root
		self.inorder(root.left)
		self.ans.append(root.data)
		self.inorder(root.right)
		return


class Solution:

	def correctBST(self, root):

		def inorderTraversal(node):
			nonlocal prev, first, middle, last
			if node:
				inorderTraversal(node.left)
				if prev and node.data < prev.data:
					if not first:
						first = prev
					middle = node
				prev = node
				inorderTraversal(node.right)
		prev = None
		first = None
		middle = None
		last = None
		inorderTraversal(root)
		if first and last:
			(first.data, last.data) = (last.data, first.data)
		elif first and middle:
			(first.data, middle.data) = (middle.data, first.data)
		return root


class Solution:

	def correctBST(self, root):
		(first, second) = (None, None)
		prev = None

		def solves(root):
			if root == None:
				return
			nonlocal first, second, prev
			solves(root.left)
			if prev != None and prev.data > root.data:
				if first == None:
					first = prev
				second = root
			prev = root
			solves(root.right)
		solves(root)
		(first.data, second.data) = (second.data, first.data)
		return root


class Solution:

	def visit(self, root, data):
		if root is None:
			return
		self.visit(root.left, data)
		data.append(root.data)
		self.visit(root.right, data)
		return

	def fix(self, root, idxes, values, precnts=0):
		if root is None:
			return 0
		num1 = self.fix(root.left, idxes, values, precnts)
		if precnts + num1 == idxes[0]:
			root.data = values[-1]
		if precnts + num1 == idxes[-1]:
			root.data = values[0]
		num2 = self.fix(root.right, idxes, values, precnts + num1 + 1)
		return num1 + 1 + num2

	def correctBST(self, root):
		if root is None:
			return
		data = []
		self.visit(root, data)
		idxes = []
		values = []
		for i in range(len(data)):
			if i == 0:
				if data[i] > data[i + 1]:
					idxes.append(i)
					values.append(data[i])
			elif i == len(data) - 1:
				if data[i] < data[i - 1]:
					idxes.append(i)
					values.append(data[i])
			elif (data[i] - data[i - 1]) * (data[i] - data[i + 1]) > 0:
				idxes.append(i)
				values.append(data[i])
		self.fix(root, idxes, values)
		return root


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

class Solution:

	def __init__(self):
		self.prev = None
		self.first = None
		self.second = None

	def inorder(self, root):
		if root is None:
			return
		self.inorder(root.left)
		if self.prev and self.prev.data > root.data:
			if not self.first:
				self.first = self.prev
			self.second = root
		self.prev = root
		self.inorder(root.right)

	def correctBST(self, root):
		self.inorder(root)
		(self.first.data, self.second.data) = (self.second.data, self.first.data)
		return root


class Solution:

	def correctBST(self, root):
		(first, second, prev) = (None, None, Node(float('-inf')))

		def inorder_traversal(node):
			nonlocal first, second, prev
			if not node:
				return
			inorder_traversal(node.left)
			if not first and prev.data > node.data:
				first = prev
			if first and prev.data > node.data:
				second = node
			prev = node
			inorder_traversal(node.right)
		inorder_traversal(root)
		(first.data, second.data) = (second.data, first.data)
		return root


class Solution:

	def correctBST(self, root):
		prev = None
		(first, second) = (None, None)

		def inorder(x):
			nonlocal prev, first, second
			if not x:
				return
			inorder(x.left)
			if prev and prev.data > x.data:
				if not first:
					(first, second) = (prev, x)
				else:
					second = x
			prev = x
			inorder(x.right)
		inorder(root)
		(first.data, second.data) = (second.data, first.data)
		return root


def inorder_traversal(root):
	if root is None:
		return []
	return inorder_traversal(root.left) + [root] + inorder_traversal(root.right)

class Solution:

	def correctBST(self, root):
		nodes = inorder_traversal(root)
		first = None
		second = None
		prev = nodes[0]
		for node in nodes[1:]:
			if node.data < prev.data:
				if first is None:
					first = prev
				second = node
			prev = node
		(first.data, second.data) = (second.data, first.data)
		return root


import math

class Solution:

	def correctBST(self, root):

		def search(root, val):
			if root == None:
				return None
			if root.data == val:
				return root
			l = search(root.left, val)
			if l != None:
				return l
			r = search(root.right, val)
			if r != None:
				return r

		def inorder(root, arr):
			if root != None:
				inorder(root.left, arr)
				arr.append(root.data)
				inorder(root.right, arr)
		arr = []
		inorder(root, arr)
		prev = -math.inf
		fir = -1
		sec = -1
		for i in range(len(arr)):
			if arr[i] < prev:
				if fir == -1:
					fir = prev
				sec = arr[i]
			prev = arr[i]
		a = search(root, fir)
		b = search(root, sec)
		(a.data, b.data) = (b.data, a.data)
		return root


from collections import deque

class Solution:

	def correctBST(self, root):
		n = list()

		def solve(node):
			nonlocal n
			if not node:
				return
			solve(node.left)
			n.append(node.data)
			solve(node.right)
		temp = root
		solve(temp)
		n.sort()
		q = deque(n)

		def correct(node):
			nonlocal n
			if not node:
				return
			correct(node.left)
			node.data = q.popleft()
			correct(node.right)
		correct(root)
		return root


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def correctBST(self, root):
		(self.first, self.middle, self.last, self.prev) = (None, None, None, None)

		def inorder(root):
			if root is None:
				return
			inorder(root.left)
			if self.prev is not None and self.prev.data > root.data:
				if self.first is not None:
					self.last = root
				else:
					(self.first, self.middle) = (self.prev, root)
			self.prev = root
			inorder(root.right)
		inorder(root)
		if self.last is None:
			(self.first.data, self.middle.data) = (self.middle.data, self.first.data)
		else:
			(self.first.data, self.last.data) = (self.last.data, self.first.data)
		return root


class Solution:

	def inorder(self, root, arr):
		if root is None:
			return
		self.inorder(root.left, arr)
		arr.append(root.data)
		self.inorder(root.right, arr)

	def update(self, root, arr):
		if root is None:
			return
		self.update(root.left, arr)
		root.data = arr.pop(-1)
		self.update(root.right, arr)

	def correctBST(self, root):
		arr = []
		self.inorder(root, arr)
		arr.sort(reverse=True)
		self.update(root, arr)
		return root


class Solution:
	i = 0

	def inorder(self, root, l):
		if root == None:
			return []
		self.inorder(root.left, l)
		l.append(root.data)
		self.inorder(root.right, l)

	def solve(self, root, l):
		if root == None:
			return None
		self.solve(root.left, l)
		root.data = l[self.i]
		self.i += 1
		self.solve(root.right, l)

	def correct(self, l):
		(f, h) = (None, None)
		for i in range(len(l) - 1):
			if l[i] > l[i + 1]:
				if f == None:
					f = i
				else:
					h = i + 1
					break
		if h == None:
			h = f + 1
		(l[f], l[h]) = (l[h], l[f])

	def correctBST(self, root):
		l = []
		self.inorder(root, l)
		self.correct(l)
		self.solve(root, l)
		return root


class Solution:

	def correctBST(self, root):

		def solve(root, first, second, third, curr):
			if root == None:
				return
			solve(root.left, first, second, third, curr)
			if curr[0] and root.data < curr[0].data:
				if first[0] == None:
					first[0] = curr[0]
					third[0] = root
				else:
					second[0] = root
			curr[0] = root
			solve(root.right, first, second, third, curr)
		(first, second, third, curr) = ([None], [None], [None], [None])
		solve(root, first, second, third, curr)
		if first[0] and second[0]:
			(first[0].data, second[0].data) = (second[0].data, first[0].data)
		elif first[0] and third[0]:
			(first[0].data, third[0].data) = (third[0].data, first[0].data)
		return root


class Solution:

	def correctBST(self, root):
		inorder = []

		def inOrder(root):
			if root is None:
				return
			inOrder(root.left)
			inorder.append(root.data)
			inOrder(root.right)
		inOrder(root)
		inorder.sort()
		self.i = 0

		def inOrder2(root):
			if root is None:
				return
			inOrder2(root.left)
			if inorder[self.i] != root.data:
				root.data = inorder[self.i]
			self.i += 1
			inOrder2(root.right)
		inOrder2(root)
		return root


class Solution:
	i = 0

	def inorder(self, root, l):
		if root == None:
			return []
		self.inorder(root.left, l)
		l.append(root.data)
		self.inorder(root.right, l)

	def solve(self, root, l):
		if root == None:
			return None
		self.solve(root.left, l)
		root.data = l[self.i]
		self.i += 1
		self.solve(root.right, l)

	def correctBST(self, root):
		l = []
		self.inorder(root, l)
		l.sort()
		self.solve(root, l)
		return root


class Solution:

	def correctBST(self, root):
		self.arr = []
		self.index = 0
		self.cus(root)
		self.arr.sort()
		self.srt(root)
		return root

	def cus(self, root):
		if root is None:
			return
		self.cus(root.left)
		self.arr.append(root.data)
		self.cus(root.right)

	def srt(self, root):
		if root is None:
			return
		self.srt(root.left)
		root.data = self.arr[self.index]
		self.index += 1
		self.srt(root.right)


class Solution:
	first = None
	second = None
	previous = None

	def inorder(self, root):
		if root == None:
			return
		self.inorder(root.left)
		if self.previous != None and root.data < self.previous.data:
			if self.first == None:
				self.first = self.previous
			self.second = root
		self.previous = root
		self.inorder(root.right)

	def correctBST(self, root):
		self.inorder(root)
		(self.first.data, self.second.data) = (self.second.data, self.first.data)
		return root


class Solution:

	def traverse(self, root, arr):
		if root == None:
			return
		self.traverse(root.left, arr)
		arr.append(root.data)
		self.traverse(root.right, arr)

	def change(self, root, a, b, rt):
		if root == None:
			return
		if root.data == a:
			rt.append(root)
		if root.data == b:
			rt.append(root)
		self.change(root.left, a, b, rt)
		self.change(root.right, a, b, rt)

	def correctBST(self, root):
		arr = []
		self.traverse(root, arr)
		a = []
		for i in range(len(arr) - 1):
			if arr[i] > arr[i + 1]:
				a.append(arr[i])
				break
		for i in range(len(arr) - 1, 0, -1):
			if arr[i - 1] > arr[i]:
				a.append(arr[i])
				break
		if len(a) == 2:
			rt = []
			self.change(root, a[0], a[1], rt)
			(rt[0].data, rt[1].data) = (rt[1].data, rt[0].data)
		return root