Given a Binary Tree, convert it to Binary Search Tree in such a way that keeps the original structure of Binary Tree intact.
 
Example 1:
Input:
      1
    /   \
   2     3
Output: 1 2 3
Example 2:
Input:
          1
       /    \
     2       3
   /        
 4       
Output: 1 2 3 4
Explanation:
The converted BST will be
        3
      /   \
    2     4
  /
 1
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function binaryTreeToBST() which takes the root of the Binary tree as input and returns the root of the BST. The driver code will print inorder traversal of the converted BST.
Expected Time Complexity: O(NLogN).
Expected Auxiliary Space: O(N).
Constraints:
1 <= Number of nodes <= 1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

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:
    # The given root is the root of the Binary Tree
    # Return the root of the generated BST
    def binaryTreeToBST(self, root):
        # code here

Solutions:
class Solution:

	def binaryTreeToBST(self, root):
		self.l = []
		self.solve(root)
		self.l.sort()
		i = [0]
		self.bst(root, i)
		return root

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

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


class Solution:

	def binaryTreeToBST(self, root):

		def storeInorder(root):
			if root == None:
				return
			storeInorder(root.left)
			ans.append(root.data)
			storeInorder(root.right)

		def arrayToBST(root, ans):
			if root == None:
				return
			arrayToBST(root.left, ans)
			val = ans.pop(0)
			root.data = val
			arrayToBST(root.right, ans)
		ans = []
		storeInorder(root)
		ans = sorted(ans)
		arrayToBST(root, ans)


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

def bst(root, arr):
	if root is None:
		return
	bst(root.left, arr)
	root.data = arr[0]
	arr.pop(0)
	bst(root.right, arr)

class Solution:

	def binaryTreeToBST(self, root):
		if root is None:
			return
		arr = []
		inorder(root, arr)
		arr.sort()
		bst(root, arr)


class Solution:

	def inorder(self, root):
		if root is None:
			return []
		return self.inorder(root.left) + [root.data] + self.inorder(root.right)

	def inorder_update(self, root, data, idx):
		if root is None:
			return
		self.inorder_update(root.left, data, idx)
		root.data = data[idx[0]]
		idx[0] += 1
		self.inorder_update(root.right, data, idx)

	def binaryTreeToBST(self, root):
		inord = self.inorder(root)
		inord.sort()
		idx = [0]
		self.inorder_update(root, inord, idx)
		return root


class Solution:

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

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

	def binaryTreeToBST(self, root):
		self.arr = []
		self.inorder_bt(root)
		self.arr.sort()
		i = [0]
		self.inorder_bst(root, i)
		return root


class Solution:

	def binaryTreeToBST(self, root):

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

		def inorder_bst(node, arr, i):
			if not node:
				return
			inorder_bst(node.left, arr, i)
			node.data = arr[i[0]]
			i[0] += 1
			inorder_bst(node.right, arr, i)
			return
		arr = []
		inorder(root)
		arr.sort()
		i = [0]
		inorder_bst(root, arr, i)
		return root


class Solution:

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

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

	def binaryTreeToBST(self, root):
		self.arr = []
		self.index = 0
		self.serialize(root)
		self.arr.sort()
		self.buildtree(root)
		return root


class Solution:

	def binaryTreeToBST(self, root):

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

		def bstconvert(root):
			if not root:
				return
			bstconvert(root.left)
			root.data = self.li.pop(0)
			bstconvert(root.right)
			return
		self.li = []
		inorder(root)
		self.li.sort()
		bstconvert(root)


class Solution:

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

	def fun1(self, root, l):
		if root == None:
			return
		self.fun1(root.left, l)
		t = l.pop()
		root.data = t
		self.fun1(root.right, l)

	def binaryTreeToBST(self, root):
		l = []
		self.fun(root, l)
		l.sort()
		l = l[::-1]
		self.fun1(root, l)
		return root


class Solution:

	def binaryTreeToBST(self, root):

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

		def constructor(root, l):
			if root == None:
				return
			constructor(root.left, l)
			root.data = l.pop(0)
			constructor(root.right, l)
		constructor(root, l)
		return root


class Solution:

	def binaryTreeToBST(self, root):

		def binary(root, lis):
			if not root:
				return lis
			binary(root.left, lis)
			lis.append(root.data)
			binary(root.right, lis)
			return lis
		lis = []
		lis = binary(root, lis)
		lis.sort()
		global i
		i = 0

		def rec(root, lis):
			global i
			if not root:
				return root
			rec(root.left, lis)
			root.data = lis[i]
			i += 1
			rec(root.right, lis)
			return root
		return rec(root, lis)


class Solution:

	def binaryTreeToBST(self, root):
		arr = []
		inorder(root, arr)
		arr.sort()
		arrtobst(root, arr)

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

def arrtobst(root, arr):
	if not root:
		return None
	arrtobst(root.left, arr)
	root.data = arr[0]
	arr.pop(0)
	arrtobst(root.right, arr)


class Solution:

	def binaryTreeToBST(self, root):
		inorder_arr = []
		self.in_order_util(root, inorder_arr)
		sorted_inorder_arr = sorted(inorder_arr)
		elements_map_dict = {}
		for i in range(0, len(inorder_arr)):
			elements_map_dict[inorder_arr[i]] = sorted_inorder_arr[i]
		traverse_queue = [root]
		while len(traverse_queue) > 0:
			size = len(traverse_queue)
			for i in range(0, size):
				element_node = traverse_queue.pop(0)
				curr_value = element_node.data
				desired_value = elements_map_dict[curr_value]
				element_node.data = desired_value
				if element_node.left is not None:
					traverse_queue.append(element_node.left)
				if element_node.right is not None:
					traverse_queue.append(element_node.right)

	def in_order_util(self, root, inorder_arr: []):
		if root is None:
			return
		self.in_order_util(root.left, inorder_arr)
		inorder_arr.append(root.data)
		self.in_order_util(root.right, inorder_arr)


class Solution:

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

		def bfs(node):
			if not node:
				return
			arr.append(node.data)
			bfs(node.left)
			bfs(node.right)
		bfs(root)
		arr.sort()

		def newTree(node, i):
			if not node:
				return 0
			l = newTree(node.left, i)
			r = newTree(node.right, i + l + 1)
			node.data = arr[i + l]
			return l + r + 1
		newTree(root, 0)
		return root


class Solution:

	def binaryTreeToBST(self, root):
		inordr = []

		def getvalue(root):
			if root == None:
				return
			inordr.append(root.data)
			getvalue(root.left)
			getvalue(root.right)
		getvalue(root)
		inordr = sorted(inordr)

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			root.data = inordr.pop(0)
			inorder(root.right)
		inorder(root)


class Solution:

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

	def arrayToBST(self, root, arr):
		if root is None:
			return
		self.arrayToBST(root.left, arr)
		root.data = arr[0]
		arr.pop(0)
		self.arrayToBST(root.right, arr)

	def binaryTreeToBST(self, root):
		arr = []
		self.store(root, arr)
		arr = sorted(arr)
		self.arrayToBST(root, arr)
		return root


class Solution:

	def __init__(self):
		self.ans = 0

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

		def inorder(root):
			if root:
				inorder(root.left)
				ans.append(root.data)
				inorder(root.right)
		inorder(root)
		ans.sort()

		def traverse(root):
			if root:
				traverse(root.left)
				root.data = ans[self.ans]
				self.ans += 1
				traverse(root.right)
		traverse(root)
		return root


class Solution:

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

	def bt2bst(self, root, li):
		if root == None:
			return root
		self.bt2bst(root.left, li)
		root.data = li[0]
		li.pop(0)
		self.bt2bst(root.right, li)
		return root

	def binaryTreeToBST(self, root):
		li = []
		li = self.generateli(root, li)
		li.sort()
		return self.bt2bst(root, li)


class Solution:

	def binaryTreeToBST(self, root):
		inorder_list = []
		inorder_list = self.inorder(root, inorder_list)
		inorder_list.sort()
		self.update(root, inorder_list)
		return root

	def update(self, root, inorder_list):
		if not root:
			return
		self.update(root.left, inorder_list)
		root.data = inorder_list[0]
		inorder_list.pop(0)
		self.update(root.right, inorder_list)
		return inorder_list

	def inorder(self, root, inorder_list):
		if not root:
			return
		self.inorder(root.left, inorder_list)
		inorder_list.append(root.data)
		self.inorder(root.right, inorder_list)
		return inorder_list


class Solution:

	def binaryTreeToBST(self, root):

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

		def atbst(root, arr):
			if not root:
				return
			atbst(root.left, arr)
			root.data = arr.pop(0)
			atbst(root.right, arr)
		arr = []
		ba(root, arr)
		arr.sort()
		atbst(root, arr)
		return root


class Solution:

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

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

	def binaryTreeToBST(self, root):
		inord = self.inorder(root)
		inord.sort()
		i = [0]
		self.inorder_to_bst(root, inord, i)
		return root


class Solution:

	def binaryTreeToBST(self, root):

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

		def copy(root, list):
			if root:
				copy(root.left, list)
				root.data = list.pop(0)
				copy(root.right, list)
			return root
		list = inorder(root, [])
		list.sort()
		return copy(root, list)


class Solution:

	def binaryTreeToBST(self, root):
		inorderd = []
		inorderd = self.inorder(root, inorderd)
		inorderd.sort()
		self.node_update(root, inorderd)
		return root

	def inorder(self, root, inorderd):
		if not root:
			return None
		self.inorder(root.left, inorderd)
		inorderd += [root.data]
		self.inorder(root.right, inorderd)
		return inorderd

	def node_update(self, root, inorderd):
		if not root:
			return None
		self.node_update(root.left, inorderd)
		root.data = inorderd[0]
		inorderd.pop(0)
		self.node_update(root.right, inorderd)
		return inorderd


class Solution:

	def binaryTreeToBST(self, root):
		l = []

		def tree(root):
			if root is None:
				return
			l.append(root.data)
			tree(root.left)
			tree(root.right)
		tree(root)
		l.sort()

		def tre(root, i):
			if root is None:
				return
			tre(root.left, i)
			root.data = l[0]
			l.pop(0)
			tre(root.right, i)
		tre(root, 0)
		return root


class Solution:

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

	def inorder(self, nodes, start, end):
		if start > end:
			return
		mid = (start + end) // 2
		node = nodes[mid]
		node.left = self.inorder(nodes, start, mid - 1)
		node.right = self.inorder(nodes, mid + 1, end)
		return node

	def inorder1(self, root, nodes):
		if not root:
			return
		self.inorder1(root.left, nodes)
		root.data = nodes[self.i]
		self.i += 1
		self.inorder1(root.right, nodes)

	def binaryTreeToBST(self, root):
		nodes = []
		self.i = 0
		self.preorder(root, nodes)
		nodes.sort()
		self.inorder1(root, nodes)
		return root


class Solution:

	def binaryTreeToBST(self, root):

		def _collect(nd):
			if not nd:
				return
			save.append(nd.data)
			_collect(nd.left)
			_collect(nd.right)

		def _inorder(nd):
			if not nd:
				return
			_inorder(nd.left)
			nd.data = save.pop()
			_inorder(nd.right)
		save = []
		_collect(root)
		save.sort(reverse=True)
		_inorder(root)
		return root


class Solution:

	def binaryTreeToBST(self, root):
		if root is None:
			return
		array = []
		array = inorder(root, array)
		array.sort()
		arrtoBst(array, root)

def arrtoBst(array, root):
	if root is None:
		return
	arrtoBst(array, root.left)
	root.data = array[0]
	array.pop(0)
	arrtoBst(array, root.right)

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


class Solution:

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

	def advanceinorder(self, root):
		if root is not None:
			self.advanceinorder(root.left)
			root.data = self.a.pop(0)
			self.advanceinorder(root.right)
			return

	def binaryTreeToBST(self, root):
		self.a = []
		self.inorder(root)
		self.a.sort()
		self.advanceinorder(root)
		return root


class Solution:

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

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

	def insertIntoTree(self, root):
		if root is None:
			return
		self.insertIntoTree(root.left)
		poped = self.nodes.pop()
		root.data = poped
		self.insertIntoTree(root.right)

	def binaryTreeToBST(self, root):
		self.getNodesList(root)
		self.nodes.sort(reverse=True)
		self.insertIntoTree(root)


class Solution:

	def binaryTreeToBST(self, root):
		inorder = []
		cur = root
		while cur:
			if not cur.left:
				inorder.append(cur.data)
				cur = cur.right
			else:
				pred = cur.left
				while pred.right and pred.right != cur:
					pred = pred.right
				if not pred.right:
					pred.right = cur
					cur = cur.left
				else:
					pred.right = None
					inorder.append(cur.data)
					cur = cur.right
		inorder.sort()
		self.ind = 0

		def fun(node):
			if not node:
				return
			fun(node.left)
			node.data = inorder[self.ind]
			self.ind += 1
			fun(node.right)
		fun(root)


class Solution:

	def binaryTreeToBST(self, root):
		arr = []
		q = []
		q.append(root)
		while len(q):
			p = q.pop(0)
			arr.append(p.data)
			if p.left:
				q.append(p.left)
			if p.right:
				q.append(p.right)
		arr.sort()
		current = root
		stack = []
		i = 0
		while 1:
			if current is not None:
				stack.append(current)
				current = current.left
			elif stack:
				p = stack.pop()
				p.data = arr[i]
				i += 1
				current = p.right
			else:
				break
		return root


def inorder(root):
	if root == None:
		return
	inorder(root.left)
	ino.append(root.data)
	inorder(root.right)

def bst(root):
	global i
	if root == None:
		return
	bst(root.left)
	root.data = ino[i]
	i += 1
	bst(root.right)

class Solution:

	def binaryTreeToBST(self, root):
		global ino
		ino = []
		inorder(root)
		ino.sort()
		global i
		i = 0
		bst(root)
		return root


class Solution:

	def binaryTreeToBST(self, root):
		arr = self.getItems(root)
		arr.sort()
		self.helper(root, arr)
		return root

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

	def getItems(self, root):
		if root is None:
			return []
		output = [root.data]
		output += self.getItems(root.left)
		output += self.getItems(root.right)
		return output


class Solution:

	def binaryTreeToBST(self, root):

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			ans.append(root.data)
			inorder(root.right)
		ans = []
		inorder(root)
		ans.sort()
		self.i = 0

		def convert(root):
			if root == None:
				return
			convert(root.left)
			root.data = ans[self.i]
			self.i += 1
			convert(root.right)
		convert(root)
		return root


class Solution:

	def binaryTreeToBST(self, root):

		def inorder_bt(root, lis):
			if not root:
				return lis
			inorder_bt(root.left, lis)
			lis.append(root.data)
			inorder_bt(root.right, lis)
			return lis
		lis = []
		lis = inorder_bt(root, lis)
		lis = sorted(lis)
		global i
		i = 0

		def inorder_bst(root, lis):
			global i
			if not root:
				return
			inorder_bst(root.left, lis)
			root.data = lis[i]
			i += 1
			inorder_bst(root.right, lis)
			return root
		return inorder_bst(root, lis)


class Solution:

	def binaryTreeToBST(self, root):

		def ino(root, a, flag):
			if root == None:
				return
			ino(root.left, a, flag)
			if flag[0] == -1:
				a.append(root.data)
			else:
				root.data = a[flag[0]]
				flag[0] += 1
			ino(root.right, a, flag)
		a = []
		flag = [-1]
		ino(root, a, flag)
		a.sort()
		flag[0] = 0
		ino(root, a, flag)
		return root


class Solution:

	def binaryTreeToBST(self, root):
		l = []

		def retrivedata(root):
			if root == None:
				return
			retrivedata(root.left)
			l.append(root.data)
			retrivedata(root.right)

		def add_data(root):
			if root == None:
				return
			add_data(root.left)
			root.data = l.pop(0)
			add_data(root.right)
		retrivedata(root)
		l.sort()
		add_data(root)


class Solution:

	def binaryTreeToBST(self, root):
		l = []

		def inorder(root, l):
			if root is None:
				return
			inorder(root.left, l)
			l.append(root.data)
			inorder(root.right, l)
			return l
		lis = inorder(root, l)
		lis.sort()

		def bst(root, lis):
			if root is None:
				return
			bst(root.left, lis)
			e = l.pop(0)
			root.data = e
			bst(root.right, lis)
			return root
		return bst(root, lis)


class Solution:
	m = 0

	def binaryTreeToBST(self, root):
		A = []
		self.x(root, A)
		A.sort()
		B = [0]
		self.atb(root, A, B)

	def atb(self, root, A, B):
		global m
		if root is None:
			return
		self.atb(root.left, A, B)
		root.data = A[B[0]]
		B[0] += 1
		self.atb(root.right, A, B)

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


class Solution:

	def binaryTreeToBST(self, root):

		def pre(root, lis):
			if root == None:
				return
			pre(root.left, lis)
			lis.append(root.data)
			pre(root.right, lis)
			return lis
		liiis = pre(root, [])
		liiis.sort()

		def make(root, liis):
			if not root:
				return None
			make(root.left, liis)
			root.data = liis[0]
			liis.pop(0)
			make(root.right, liis)
			return root
		return make(root, liiis)


class Solution:

	def binaryTreeToBST(self, root):
		arr = []
		ind = [-1]

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

		def dfs(root):
			if not root:
				return
			dfs(root.left)
			ind[0] += 1
			root.data = arr[ind[0]]
			dfs(root.right)
		traversal(root)
		arr.sort()
		dfs(root)
		return root


class Solution:

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

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

		def inorder2(node):
			if not node:
				return
			inorder2(node.left)
			node.data = arr.pop()
			inorder2(node.right)
		inorder(root)
		arr.sort(reverse=True)
		inorder2(root)
		return root


class Solution:

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

	def InOrder(self, Node):
		if Node == None:
			return
		self.InOrder(Node.left)
		self.inorder.append(Node)
		self.InOrder(Node.right)
		return

	def SortNodeVal(self):
		NodeVal = []
		for i in range(0, len(self.inorder)):
			NodeVal.append(self.inorder[i].data)
		NodeVal.sort()
		for i in range(0, len(self.inorder)):
			self.inorder[i].data = NodeVal[i]

	def binaryTreeToBST(self, root):
		self.InOrder(root)
		self.SortNodeVal()
		return root


class Solution:

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

	def inorderbst(self, root, ans):
		if root is None:
			return
		else:
			self.inorderbst(root.left, ans)
			root.data = ans[0]
			ans.pop(0)
			self.inorderbst(root.right, ans)

	def binaryTreeToBST(self, root):
		ans = []
		self.inorder(root, ans)
		ans.sort()
		self.inorderbst(root, ans)
		return root


class Solution:

	def binaryTreeToBST(self, root):
		a = []
		self.inorder(root, a)
		a.sort()

		def dfs(root, a):
			if root:
				dfs(root.left, a)
				root.data = a.pop(0)
				dfs(root.right, a)
		dfs(root, a)
		return root

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


class Solution:

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

	def binaryTreeToBST(self, root):
		inorder = []
		self.inorder(root, inorder)
		vals = [node.data for node in inorder]
		vals.sort()
		for i in range(len(vals)):
			inorder[i].data = vals[i]
		return root


class Solution:

	def binaryTreeToBST(self, root):

		def func1(ans, root):
			if root is None:
				return
			func1(ans, root.left)
			root.data = ans[0]
			ans.pop(0)
			func1(ans, root.right)

		def func(ans, root):
			if root is None:
				return
			func(ans, root.left)
			ans.append(root.data)
			func(ans, root.right)
		ans = []
		func(ans, root)
		ans.sort()
		func1(ans, root)


from collections import deque

def inorder(root, ans):
	if root:
		inorder(root.left, ans)
		ans.append(root.data)
		inorder(root.right, ans)
	return ans

def btbst(root, ans):
	if root:
		btbst(root.left, ans)
		root.data = ans.popleft()
		btbst(root.right, ans)

class Solution:

	def binaryTreeToBST(self, root):
		ans = []
		a = inorder(root, ans)
		a = sorted(a)
		btbst(root, deque(a))
		return root


class Solution:

	def binaryTreeToBST(self, root):
		res = self.inorder(root)
		res.sort()
		root = self.arrayToBST(root, res)

	def inorder(self, root):
		if root is None:
			return []
		return self.inorder(root.left) + [root.data] + self.inorder(root.right)

	def arrayToBST(self, root, res):
		if not root:
			return
		self.arrayToBST(root.left, res)
		root.data = res[0]
		res.pop(0)
		self.arrayToBST(root.right, res)


class Solution:

	def binaryTreeToBST(self, root):

		def BTtoarray(root, array):
			if not root:
				return
			BTtoarray(root.left, array)
			array.append(root.data)
			BTtoarray(root.right, array)

		def arrayToBST(array, root):
			if not root:
				return
			arrayToBST(array, root.left)
			root.data = array.pop(0)
			arrayToBST(array, root.right)
		if not root:
			return
		inorder = []
		BTtoarray(root, inorder)
		inorder.sort()
		arrayToBST(inorder, root)


class Solution:

	def binaryTreeToBST(self, root):

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

		def countNodes(root):
			if not root:
				return 0
			return 1 + countNodes(root.left) + countNodes(root.right)

		def arrayToBST(inorder, root):
			if not root:
				return
			arrayToBST(inorder, root.left)
			root.data = inorder.pop(0)
			arrayToBST(inorder, root.right)
		if not root:
			return
		inorder = []
		storeInorder(root, inorder)
		inorder.sort()
		arrayToBST(inorder, root)


class Solution:

	def binaryTreeToBST(self, root):

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

		def countNodes(root):
			if root is None:
				return 0
			return 1 + countNodes(root.left) + countNodes(root.right)

		def arrayToBST(inorder, root):
			if root is None:
				return
			arrayToBST(inorder, root.left)
			root.data = inorder.pop(0)
			arrayToBST(inorder, root.right)
		if root is None:
			return
		n = countNodes(root)
		inorder = []
		storeInorder(inorder, root)
		inorder.sort()
		arrayToBST(inorder, root)


class Solution:

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

		def dfs(root):
			if root == None:
				return
			dfs(root.left)
			res.append(root)
			dfs(root.right)
		dfs(root)
		res2 = sorted([n.data for n in res])
		for i in range(len(res)):
			res[i].data = res2[i]
		return root


class Solution:

	def helper_find_values(self, root, val):
		if root:
			self.helper_find_values(root.left, val)
			val.append(root.data)
			self.helper_find_values(root.right, val)

	def place_data_Tree(self, root, val, index):
		if root:
			self.place_data_Tree(root.left, val, index)
			root.data = val[index[0]]
			index[0] += 1
			self.place_data_Tree(root.right, val, index)

	def binaryTreeToBST(self, root):
		val = []
		self.helper_find_values(root, val)
		val.sort()
		self.place_data_Tree(root, val, [0])


class Solution:

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

		def inorder(root):
			nonlocal res
			if not root:
				return root
			inorder(root.left)
			res.append(root.data)
			inorder(root.right)
		inorder(root)
		res.sort()
		i = 0

		def dfs(root):
			nonlocal i
			if not root:
				return root
			dfs(root.left)
			root.data = res[i]
			i += 1
			dfs(root.right)
		dfs(root)


class Solution:

	def binaryTreeToBST(self, root):

		def dfs(root, ans):
			if not root:
				return
			ans.append(root.data)
			dfs(root.left, ans)
			dfs(root.right, ans)
		ans = []
		dfs(root, ans)
		ans.sort()

		def ino(root, ans):
			if not root:
				return
			ino(root.left, ans)
			root.data = ans.pop(0)
			ino(root.right, ans)
		ino(root, ans)
		return root


class Solution:

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

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

	def binaryTreeToBST(self, root):
		ans = []
		self.inorder(root, ans)
		ans = sorted(ans)
		i = [0]
		self.create(root, ans, i)
		return root


class Solution:

	def inorder(self, root, result):
		if not root:
			return result
		result.append(root.data)
		self.inorder(root.left, result)
		self.inorder(root.right, result)
		return result

	def createBST(self, root, result):
		if not root or not result:
			return None
		self.createBST(root.left, result)
		root.data = result.pop(0)
		self.createBST(root.right, result)
		return root

	def binaryTreeToBST(self, root):
		inorder = self.inorder(root, [])
		inorder.sort()
		return self.createBST(root, inorder)