You are given the root of a binary search tree(BST), where exactly two nodes were swapped by mistake. 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. All changes must be reflected in the original linked list.
 
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 not return anything, all the changes must be done in the existing tree only. BST will then be checked by driver code and 0 or 1 will be printed.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ Number of nodes ≤ 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Data structures

Range queries

Starter code: #User function Template for python3





#Function to fix a given BST where two nodes are swapped.  

class Solution:

    def correctBST(self, root):

    # code here



Solutions:
class Solution:

	def inorder(self, root):
		if root is None:
			return
		self.inorder(root.left)
		if self.prev is None:
			self.prev = root
		else:
			if self.prev.data > root.data:
				self.possibles.append(self.prev)
				self.possibles.append(root)
			self.prev = root
		if len(self.possibles) == 4:
			return
		self.inorder(root.right)

	def correctBST(self, root):
		self.prev = None
		self.possibles = []
		self.inorder(root)
		node1 = self.possibles[0]
		node2 = self.possibles[-1]
		(node1.data, node2.data) = (node2.data, node1.data)
		return root


class Solution:

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

	def correctBST(self, root):
		t = []
		q = []
		j = []
		self.solve(root, q, t)
		for i in range(len(q) - 1):
			if q[i] > q[i + 1]:
				j.append(i)
				j.append(i + 1)
		(t[j[0]].data, t[j[len(j) - 1]].data) = (t[j[len(j) - 1]].data, t[j[0]].data)


class Solution:

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

	def findNodes(self, root):
		if root is None:
			return True
		self.findNodes(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.findNodes(root.right)

	def swapNodes(self, n1, n2):
		(n1.data, n2.data) = (n2.data, n1.data)

	def correctBST(self, root):
		self.findNodes(root)
		self.swapNodes(self.first, self.second)


class Solution:

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

		def find(root):
			if root:
				find(root.left)
				ans.append(root)
				find(root.right)
			return
		find(root)
		a = []
		for i in range(1, len(ans)):
			if ans[i - 1].data > ans[i].data:
				if not a:
					a.append(ans[i])
					a.append(ans[i - 1])
				else:
					a[0] = ans[i]
		(a[0].data, a[1].data) = (a[1].data, a[0].data)


class Pointers:

	def __init__(self):
		self.f = None
		self.m = None
		self.l = None
		self.p = Node(float('-inf'))

class Solution:

	def correctBST(self, root):
		pointer = Pointers()

		def swapBST(root):
			if root == None:
				return None
			swapBST(root.left)
			if pointer.p != None and root.data < pointer.p.data:
				if pointer.f == None and pointer.m == None:
					pointer.f = pointer.p
					pointer.m = root
				else:
					pointer.l = root
			pointer.p = root
			swapBST(root.right)
		swapBST(root)
		if pointer.f and pointer.l:
			(pointer.f.data, pointer.l.data) = (pointer.l.data, pointer.f.data)
		else:
			(pointer.f.data, pointer.m.data) = (pointer.m.data, pointer.f.data)
		return root


class Solution:
	prev = None
	first = None
	second = None

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

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


class Solution:

	def check(self, first, second, root, pre):
		if first[0] == None and root.data < pre.data:
			first[0] = pre
		if first[0] and root.data < pre.data:
			second[0] = root

	def correctBST(self, root):
		if root.left == None and (not root.right):
			return
		current = root
		predecessor = Node(-float('inf'))
		first_mistake = [None]
		second_mistake = [None]
		while current:
			if current.left == None:
				self.check(first_mistake, second_mistake, current, predecessor)
				predecessor = current
				current = current.right
			else:
				left = current.left
				while left.right and left.right != current:
					left = left.right
				if left.right == None:
					left.right = current
					current = current.left
				else:
					left.right = None
					self.check(first_mistake, second_mistake, current, predecessor)
					predecessor = current
					current = current.right
		(first_mistake[0].data, second_mistake[0].data) = (second_mistake[0].data, first_mistake[0].data)


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):
		self.swapped = [None, None]
		self.prev = Node(float('-inf'))

		def inorder(node):
			if node is None:
				return
			inorder(node.left)
			if self.swapped[0] is None and self.prev.data >= node.data:
				self.swapped[0] = self.prev
			if self.swapped[0] is not None and self.prev.data >= node.data:
				self.swapped[1] = node
			self.prev = node
			inorder(node.right)
		inorder(root)
		(self.swapped[0].data, self.swapped[1].data) = (self.swapped[1].data, self.swapped[0].data)


class Solution:

	def correctBST(self, root):
		first = [None]
		mid = [None]
		last = [None]
		pre = [None]

		def ino(r):
			if not r:
				return
			ino(r.left)
			if pre[0] != None and r.data < pre[0].data:
				if first[0] == None:
					first[0] = pre[0]
					mid[0] = r
				else:
					last[0] = r
			pre[0] = r
			ino(r.right)
		ino(root)
		if first[0] != None and last[0] == None:
			t = first[0].data
			first[0].data = mid[0].data
			mid[0].data = t
		elif first[0] != None and last[0] != None:
			t = first[0].data
			first[0].data = last[0].data
			last[0].data = t


class Solution:

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

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

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


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)


class Solution:

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

	def correctUtil(self, root, swap_1, swap_2):
		if root is None:
			return
		self.correctUtil(root.left, swap_1, swap_2)
		if root.data in [swap_1, swap_2]:
			root.data ^= swap_1 ^ swap_2
		self.correctUtil(root.right, swap_1, swap_2)
		return

	def correctBST(self, root):
		self.inorder = []
		self.getInorder(root)
		(swap_1, swap_2) = (-1, -1)
		for i in range(len(self.inorder) - 1):
			if self.inorder[i] > self.inorder[i + 1]:
				if swap_1 == -1:
					swap_1 = self.inorder[i]
					swap_2 = self.inorder[i + 1]
				else:
					swap_2 = self.inorder[i + 1]
		self.correctUtil(root, swap_1, swap_2)


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.l = None
		self.r = None
		self.mr = None
		self.bst(root)
		l = self.l.data
		r = self.r.data
		self.l.data = r
		self.r.data = l
		return root

	def bst(self, root):
		if root == None:
			return
		self.bst(root.left)
		if self.mr != None and root.data < self.mr.data:
			if self.l == None:
				self.l = self.mr
			self.r = root
		self.mr = root
		self.bst(root.right)


class Solution:

	def correctBST(self, root):
		v = []
		self.inorder(root, v)
		v.sort()
		self.check(root, v)

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

	def check(self, root, v):
		if root == None:
			return
		self.check(root.left, v)
		if v[0] != root.data:
			root.data = v[0]
		v.pop(0)
		self.check(root.right, v)


class Solution:

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

		def help(r):
			if r:
				help(r.left)
				res.append(r)
				help(r.right)
		help(root)
		n = len(res) - 1
		(i, j) = (0, n)
		while i <= n and res[i].data < res[i + 1].data:
			i += 1
		while j > 1 and res[j].data > res[j - 1].data:
			j -= 1
		(res[i].data, res[j].data) = (res[j].data, res[i].data)


class Solution:

	def correctBST(self, root):

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			if self.prev and root.data < self.prev.data:
				if self.left:
					self.first = self.prev
					self.second = root
					self.left = 0
				else:
					self.last = root
			self.prev = root
			inorder(root.right)
		self.left = 1
		self.first = self.second = self.last = -1
		self.prev = Node(float('-inf'))
		inorder(root)
		if self.last == -1:
			(self.first.data, self.second.data) = (self.second.data, self.first.data)
		else:
			(self.first.data, self.last.data) = (self.last.data, self.first.data)


class Solution:

	def correctBST(self, root):
		s = []
		cur = root
		while cur:
			s.append(cur)
			cur = cur.left
		prev = first = second = None
		while s:
			elem = s.pop()
			if prev and prev.data > elem.data:
				if not first:
					first = prev
				second = elem
			prev = elem
			cur = elem.right
			while cur:
				s.append(cur)
				cur = cur.left
		(first.data, second.data) = (second.data, first.data)


class Solution:

	def correctBST(self, root):
		temp = []
		srt = []

		def f(root):
			if not root:
				return None
			if root:
				f(root.left)
				temp.append(root)
				f(root.right)

		def values(root):
			if not root:
				return None
			if root:
				values(root.left)
				srt.append(root.data)
				values(root.right)
		f(root)
		values(root)
		srt = sorted((root.data for root in temp))
		for i in range(len(srt)):
			temp[i].data = srt[i]


class Solution:

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

		def inorder(root):
			nonlocal a, b, prev
			if root:
				inorder(root.left)
				if root.data < prev.data:
					if not a:
						a = prev
					b = root
				prev = root
				inorder(root.right)
		inorder(root)
		(a.data, b.data) = (b.data, a.data)


class Solution:

	def correctBST(self, root):

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


class Solution:

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

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


class Solution:

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

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


class Solution:

	def correctBST(self, root):
		arr = [None, None, None, None]
		self.Util(root, arr)
		if arr[1] and arr[3]:
			(arr[1].data, arr[3].data) = (arr[3].data, arr[1].data)
		elif arr[1] and arr[2]:
			(arr[1].data, arr[2].data) = (arr[2].data, arr[1].data)
		return root

	def Util(self, root, arr):
		if not root:
			return
		self.Util(root.left, arr)
		if arr[0] and arr[0].data > root.data:
			if not arr[1]:
				arr[1] = arr[0]
				arr[2] = root
			else:
				arr[3] = root
		arr[0] = root
		self.Util(root.right, arr)


class Solution:

	def correctBST(self, root):
		curr = root
		first = None
		mid = None
		last = None
		inorder = None
		while curr:
			if curr.left == None:
				if inorder != None and inorder.data > curr.data and (first == None):
					first = inorder
					mid = curr
				elif first != None and inorder.data > curr.data:
					last = curr
				inorder = curr
				curr = curr.right
			else:
				prev = curr.left
				while prev.right != None and prev.right != curr:
					prev = prev.right
				if prev.right == None:
					prev.right = curr
					curr = curr.left
				else:
					prev.right = None
					if inorder != None and inorder.data > curr.data and (first == None):
						first = inorder
						mid = curr
					elif first != None and inorder.data > curr.data:
						last = curr
					inorder = curr
					curr = curr.right
		if last == None:
			(first.data, mid.data) = (mid.data, first.data)
		else:
			(first.data, last.data) = (last.data, first.data)


class Solution:

	def correctBST(self, root):
		prev = None
		first = None
		second = None
		stack = []
		while stack or root:
			while root:
				stack.append(root)
				root = root.left
			root = stack.pop()
			if prev and prev.data > root.data:
				if not first:
					first = prev
				second = root
			prev = root
			root = root.right
		(first.data, second.data) = (second.data, first.data)


class Solution:

	def correctBST(self, root):

		def in_(root):
			if root == None:
				return
			in_(root.left)
			if ne[0] is not None and root.data < ne[0].data:
				if first[0] == None:
					first[0] = ne[0]
					prev[0] = root
				else:
					sec[0] = root
			else:
				ne[0] = root
			in_(root.right)
		first = [None]
		sec = [None]
		prev = [None]
		ne = [None]
		in_(root)
		if first[0] and sec[0]:
			t = first[0].data
			first[0].data = sec[0].data
			sec[0].data = t
		elif first[0] and prev[0]:
			t = first[0].data
			first[0].data = prev[0].data
			prev[0].data = t


class Solution:

	def correctBST(self, root):
		if not (root.left or root.right):
			return root
		(prev, first, second) = ([None], [None], [None])
		self.rec(root, prev, first, second)
		(first[0].data, second[0].data) = (second[0].data, first[0].data)
		return root

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


class Solution:

	def inorder(self, root, A, __map):
		if not root:
			return
		__map[root.data] = root
		self.inorder(root.left, A, __map)
		A.append(root.data)
		self.inorder(root.right, A, __map)

	def correctBST(self, root):
		A = []
		__Map = {}
		self.inorder(root, A, __Map)
		sA = A.copy()
		sA.sort()
		for i in range(len(A)):
			if A[i] != sA[i]:
				__Map[A[i]].data = sA[i]
				__Map[sA[i]].data = A[i]
				break


import sys

class Solution:

	def correctBST(self, root):
		if not root:
			return None
		prev = Node(-sys.maxsize)
		first = None
		second = None
		curr = root
		while curr:
			if curr.left == None:
				if prev.data > curr.data:
					if first == None:
						first = prev
						second = curr
					else:
						second = curr
				prev = curr
				curr = curr.right
			else:
				rootrightmost = curr.left
				while rootrightmost.right and rootrightmost.right != curr:
					rootrightmost = rootrightmost.right
				if rootrightmost.right == None:
					rootrightmost.right = curr
					curr = curr.left
				else:
					rootrightmost.right = None
					if prev.data > curr.data:
						if first == None:
							first = prev
							second = curr
						else:
							second = curr
					prev = curr
					curr = curr.right
		(first.data, second.data) = (second.data, first.data)


class Solution:

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

		def solve(r):
			if r is None:
				return
			solve(r.left)
			if prev[0] != None and r.data < prev[0].data:
				if first[0] == None:
					first[0] = prev[0]
					second[0] = r
				else:
					third[0] = r
			prev[0] = r
			solve(r.right)
		solve(root)
		if third[0] != None:
			t = first[0].data
			first[0].data = third[0].data
			third[0].data = t
		else:
			t = first[0].data
			first[0].data = second[0].data
			second[0].data = t


class Solution:

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

	def fix_inorder(self, root, arr):
		if root:
			self.fix_inorder(root.left, arr)
			root.data = arr.pop(0)
			self.fix_inorder(root.right, arr)

	def correctBST(self, root):
		arr = list()
		self.inorder(root, arr)
		self.fix_inorder(root, sorted(arr))
		return root


class Solution:

	def correctBST(self, root):
		self.temp = []

		def dfs(node):
			if not node:
				return
			dfs(node.left)
			self.temp.append(node)
			dfs(node.right)
		dfs(root)
		srt = sorted((n.data for n in self.temp))
		for i in range(len(srt)):
			self.temp[i].data = srt[i]


class Solution:
	(big, small, prev) = (None, None, None)

	def correctBST(self, rt):

		def traverse(root):
			if root:
				traverse(root.left)
				if self.prev and self.prev.data > root.data:
					self.small = root
					if not self.big:
						self.big = self.prev
				self.prev = root
				traverse(root.right)
		traverse(rt)
		(self.big.data, self.small.data) = (self.small.data, self.big.data)


import math

class Solution:

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

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

	def find(self, root, value):
		if root.data == value:
			return root
		left = None
		right = None
		if root.left != None:
			left = self.find(root.left, value)
		if root.right != None:
			right = self.find(root.right, value)
		return left or right

	def correctBST(self, root):
		self.inorder(root)
		n = len(self.arr)
		value = -1
		for i in range(n - 1):
			if self.arr[i] > self.arr[i + 1]:
				value = self.arr[i]
				break
		if value == -1:
			value = self.arr[-1]
		svalue = -1
		for i in reversed(range(1, n)):
			if self.arr[i] < self.arr[i - 1]:
				svalue = self.arr[i]
				break
		if svalue == -1:
			svalue = self.arr[0]
		f = self.find(root, value)
		s = self.find(root, svalue)
		f.data = svalue
		s.data = value


class Solution:

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

	def correctBST(self, root):
		prev = [None]
		first = [None]
		middle = [None]
		last = [None]
		self.inorder(root, prev, first, middle, last)
		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)


class NodesInfo:

	def __init__(self):
		self.prev = Node(float('-inf'))
		self.first = None
		self.second = None

class Solution:

	def correctBST(self, root):
		nodesInfo = NodesInfo()
		self.correctBSTUtil(root, nodesInfo)
		(nodesInfo.first.data, nodesInfo.second.data) = (nodesInfo.second.data, nodesInfo.first.data)

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


class Solution:

	def correctBST(self, root):
		curr = root
		(pre, a, b) = (None, None, None)
		while curr is not None:
			left = curr.left
			if left is None:
				if pre is not None and pre.data > curr.data:
					if a is None:
						a = pre
					b = curr
				pre = curr
				curr = curr.right
			else:
				rightMost = self.getRightMostNode(left, curr)
				if rightMost.right is None:
					rightMost.right = curr
					curr = curr.left
				else:
					rightMost.right = None
					if pre is not None and pre.data > curr.data:
						if a is None:
							a = pre
						b = curr
					pre = curr
					curr = curr.right
		if a is not None:
			(a.data, b.data) = (b.data, a.data)
		return root

	def getRightMostNode(self, l, c):
		while l.right is not None and l.right != c:
			l = l.right
		return l


class Solution:

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

		def traverse(root):
			if root == None:
				return
			traverse(root.left)
			if self.prev != None and self.prev.data > root.data:
				if self.first == None:
					self.first = self.prev
				self.second = root
			self.prev = root
			traverse(root.right)
		traverse(root)
		if self.first != None and self.second != None:
			temp = self.first.data
			self.first.data = self.second.data
			self.second.data = temp


class Solution:

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

		def correct(root):
			if root == None:
				return
			correct(root.left)
			if self.previous != None and self.previous.data > root.data:
				if self.first == None:
					self.first = self.previous
				self.second = root
			self.previous = root
			correct(root.right)
		correct(root)
		if self.first != None and self.second != None:
			temp = self.first.data
			self.first.data = self.second.data
			self.second.data = temp


class Solution:

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

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

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


class Solution:

	def correctBST(self, root):

		def getNumbers(root):
			nonlocal firstNode, secondNode, prev
			if not root:
				return
			getNumbers(root.left)
			if prev and prev.data > root.data:
				if not firstNode:
					firstNode = prev
				secondNode = root
			prev = root
			getNumbers(root.right)
		firstNode = secondNode = prev = None
		getNumbers(root)
		temp = firstNode.data
		firstNode.data = secondNode.data
		secondNode.data = temp
		return root


class Solution:

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

		def inorder(root):
			nonlocal arr
			if root != None:
				inorder(root.left)
				arr.append(root)
				inorder(root.right)
		inorder(root)
		n = len(arr)
		f_index = 0
		s_index = n - 1
		for i in range(1, n):
			if arr[i - 1].data > arr[i].data:
				f_index = i - 1
				break
		for j in range(n - 2, -1, -1):
			if arr[j].data > arr[j + 1].data:
				s_index = j + 1
				break
		(arr[f_index].data, arr[s_index].data) = (arr[s_index].data, arr[f_index].data)


class Solution:

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

	def solve(self, root):
		if root != None:
			self.solve(root.left)
			if self.prev != None and root.data < self.prev.data:
				if self.first == None:
					self.first = self.prev
				self.second = root
			self.prev = root
			self.solve(root.right)

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


class Solution:

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

	def fix(self, root, l):
		if root:
			self.fix(root.left, l)
			if root.data != l[0]:
				root.data = l[0]
			l.pop(0)
			self.fix(root.right, l)

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


class Solution:

	def search(self, r, key, f):
		if r == None:
			return None
		if r.data == key:
			f = r
			return f
		left = self.search(r.left, key, f)
		if left:
			return left
		right = self.search(r.right, key, f)
		return right

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

	def correctBST(self, root):
		l = []
		self.inorder(root, l)
		t = sorted(l)
		for i in range(len(l)):
			if l[i] != t[i]:
				a = l[i]
				b = t[i]
		f = None
		g = None
		f = self.search(root, a, f)
		g = self.search(root, b, g)
		(f.data, g.data) = (g.data, f.data)
		return root


class Solution:

	def ino(self, root):
		ans = []
		if root:
			ans += self.ino(root.left)
			ans.append(root.data)
			ans += self.ino(root.right)
		return ans

	def correctBST(self, root):
		l = self.ino(root)
		l.sort()

		def update(root):
			if root:
				update(root.left)
				root.data = l[0]
				l.pop(0)
				update(root.right)
		update(root)
		return root


class Solution:

	def correctBST(self, root):
		global list1
		list1 = []
		self.inOrder(root)
		sorted_list = sorted(list1, key=lambda x: x.data)
		for i in range(len(list1)):
			if sorted_list[i] != list1[i]:
				(sorted_list[i].data, list1[i].data) = (list1[i].data, sorted_list[i].data)
				return

	def inOrder(self, root):
		global list1
		if root is None:
			return
		self.inOrder(root.left)
		list1.append(root)
		self.inOrder(root.right)


class Solution:

	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)

	def correctBSTUtil(self, root, first, middle, last, prev):
		if root:
			self.correctBSTUtil(root.left, first, middle, last, prev)
			if prev[0] and prev[0].data > root.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)


class Solution:
	previousNode = None
	firstNode = None
	secondNode = None

	def correctBSTUtil(self, root):
		if root is None:
			return
		self.correctBSTUtil(root.left)
		if self.previousNode is not None and root.data < self.previousNode.data:
			if self.firstNode is None:
				self.firstNode = self.previousNode
			self.secondNode = root
		self.previousNode = root
		self.correctBSTUtil(root.right)

	def correctBST(self, root):
		self.correctBSTUtil(root)
		if self.firstNode is not None:
			temp = self.firstNode.data
			self.firstNode.data = self.secondNode.data
			self.secondNode.data = temp
		return root


import math

class Solution:

	def __init__(self):
		self.first = None
		self.sec = None
		self.prevNode = Node(-math.inf)

	def inOT(self, root):
		if root == None:
			return
		self.inOT(root.left)
		if root.data < self.prevNode.data:
			if self.first == None:
				self.first = self.prevNode
			self.sec = root
		self.prevNode = root
		self.inOT(root.right)

	def correctBST(self, root):
		self.inOT(root)
		(self.first.data, self.sec.data) = (self.sec.data, self.first.data)


from math import inf

class Solution:

	def correctBST(self, root):
		(min_stack, max_stack) = ([], [])

		def push_all_left(node):
			while node:
				min_stack.append(node)
				node = node.left

		def push_all_right(node):
			while node:
				max_stack.append(node)
				node = node.right
		push_all_left(root)
		push_all_right(root)
		(curr_min, curr_max) = (Node(-inf), Node(inf))
		while min_stack and min_stack[-1].data > curr_min.data:
			curr_min = min_stack.pop()
			push_all_left(curr_min.right)
		while max_stack and max_stack[-1].data < curr_max.data:
			curr_max = max_stack.pop()
			push_all_right(curr_max.left)
		(curr_min.data, curr_max.data) = (curr_max.data, curr_min.data)


class Solution:

	def correctBSTutil(self, root, prev, first, second, third):
		if not root:
			return
		self.correctBSTutil(root.left, prev, first, second, third)
		temp = root.data
		if prev[0] and (not first[0]):
			if temp < prev[0].data:
				first[0] = prev[0]
				second[0] = root
		if prev[0] and first[0]:
			if temp < prev[0].data:
				third[0] = root
		prev[0] = root
		self.correctBSTutil(root.right, prev, first, second, third)

	def correctBST(self, root):
		(first, second, third, prev) = ([None], [None], [None], [None])
		self.correctBSTutil(root, prev, first, second, third)
		if third[0]:
			(first[0].data, third[0].data) = (third[0].data, first[0].data)
		else:
			(first[0].data, second[0].data) = (second[0].data, first[0].data)


class Solution:

	def correctBST(self, root):
		ans = [None, None, None]

		def inorder(nod):
			if nod is None:
				return
			inorder(nod.left)
			if ans[0] != None:
				if ans[1] == None:
					if nod.data < ans[0].data:
						ans[1] = ans[0]
				elif ans[1] != None and ans[2] is None:
					if nod.data > ans[0].data:
						ans[2] = ans[0]
				elif ans[2] != None and nod.data < ans[0].data:
					ans[2] = nod
			ans[0] = nod
			inorder(nod.right)
		inorder(root)
		if ans[2] is None:
			(ans[0].data, ans[1].data) = (ans[1].data, ans[0].data)
		else:
			(ans[1].data, ans[2].data) = (ans[2].data, ans[1].data)
		return root


class Solution:

	def correctBST(self, root):

		def my(root):
			if not root:
				return
			my(root.left)
			res.append(root.data)
			my(root.right)

		def correct(root):
			if not root:
				return
			correct(root.left)
			if root.data != res2[0]:
				root.data = min(op)
				op.remove(min(op))
			res2.pop(0)
			correct(root.right)
		res = []
		my(root)
		res2 = res[:]
		res2.sort()
		op = []
		for i in range(len(res)):
			if res[i] != res2[i]:
				op.append(res[i])
				op.append(res2[i])
				break
		correct(root)


class Solution:

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

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

	def correctBST(self, root):
		self.inOrder(root)
		if self.first and self.second:
			sec = self.second.data
			self.second.data = self.first.data
			self.first.data = sec
		return root


class Solution:

	def solve(self, root, In):
		if root == None:
			return
		self.solve(root.left, In)
		In.append(root)
		self.solve(root.right, In)

	def correctBST(self, root):
		In = []
		self.solve(root, In)
		i = 0
		j = 1
		flag = 0
		f1 = None
		f2 = None
		while j < len(In):
			if In[i].data > In[j].data:
				if flag == 0:
					f1 = In[i]
					f2 = In[j]
					flag = 1
				else:
					f2 = In[j]
			i += 1
			j += 1
		(f1.data, f2.data) = (f2.data, f1.data)


class Solution:

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

		def inorder(root):
			if not root:
				return
			inorder(root.left)
			arr.append(root.data)
			inorder(root.right)
			return
		nodes = [None, None]

		def find(root, ele1, ele2):
			if not root:
				return
			if root.data == ele1:
				nodes[0] = root
			elif root.data == ele2:
				nodes[1] = root
			find(root.left, ele1, ele2)
			find(root.right, ele1, ele2)
			return
		inorder(root)
		n = len(arr)
		fault = -1
		for i in range(n - 1):
			if arr[i] > arr[i + 1]:
				fault = i
				break
		ele1 = arr[fault]
		ele2 = 0
		second = -1
		for j in range(fault + 1, n):
			if arr[j] > ele1:
				second = j - 1
				break
		ele2 = arr[second]
		small = min(arr) - 1
		find(root, ele1, ele2)
		(nodes[0].data, nodes[1].data) = (nodes[1].data, nodes[0].data)
		return


class Solution:

	def correctBST(self, root):
		first = second = None
		sort_arr = []

		def traverse(node):
			if node.left:
				traverse(node.left)
			sort_arr.append(node)
			if node.right:
				traverse(node.right)
		traverse(root)
		for i in range(1, len(sort_arr)):
			if sort_arr[i].data > sort_arr[i - 1].data:
				continue
			elif first != None:
				second = i
			else:
				first = i - 1
				second = i
		(sort_arr[first].data, sort_arr[second].data) = (sort_arr[second].data, sort_arr[first].data)
		return root


class Solution:

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

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

		def change(root, ch, ele):
			if not root:
				return False
			if root.data == ele:
				root.data = ch
				return True
			l = change(root.left, ch, ele)
			if l:
				return True
			r = change(root.right, ch, ele)
			if r:
				return True
			return False
		inorder(root)
		n = len(arr)
		fault = -1
		for i in range(n - 1):
			if arr[i] > arr[i + 1]:
				fault = i
				break
		ele1 = arr[fault]
		ele2 = 0
		second = -1
		for j in range(fault + 1, n):
			if arr[j] > ele1:
				second = j - 1
				break
		ele2 = arr[second]
		small = min(arr) - 1
		change(root, small, ele1)
		change(root, ele1, ele2)
		change(root, ele2, small)
		return