Given a Binary Search Tree, modify the given BST such that it is balanced and has minimum possible height.
Examples :
Input:
       30
      /
     20
    /
   10
Output:
     20
   /   \
 10     30
Input:
         4
        /
       3
      /
     2
    /
   1
Output:
      3            3           2
    /  \         /  \        /  \
   1    4   OR  2    4  OR  1    3   OR ..
    \          /                   \
     2        1                     4 
Your Task:
The task is to complete the function buildBalancedTree() which takes root as the input argument and returns the root of tree after converting the given BST into a balanced BST with minimum possible height. The driver code will print the height of the updated tree in output itself. 
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Here N denotes total number of nodes in given BST.
Constraints:
1<=N<=200

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Range queries

Starter code: #User function Template for python3



class Solution:

    def buildBalancedTree(self,root):

        #code here

Solutions:
class Solution:

	def buildBalancedTree(self, root):

		def constructBST(arr):
			if arr:
				mid = len(arr) // 2
				root = Node(arr[mid])
				root.left = constructBST(arr[:mid])
				root.right = constructBST(arr[mid + 1:])
				return root

		def getValueFromBT(root):
			if root == None:
				return
			self.val.append(root.data)
			getValueFromBT(root.left)
			getValueFromBT(root.right)
		self.val = []
		getValueFromBT(root)
		self.val = sorted(self.val)
		return constructBST(self.val)


class Solution:

	def buildBalancedTree(self, root):
		arr = self.inorder(root, [])
		root = self.func(arr)
		return root

	def func(self, arr):
		if not arr:
			return
		n = len(arr) // 2
		root = Node(arr[n])
		root.left = self.func(arr[:n])
		root.right = self.func(arr[n + 1:])
		return root

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


class Solution:

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

	def create_bst(self, arr, start, end):
		if start > end:
			return
		mid = start + (end - start) // 2
		root = Node(arr[mid])
		root.left = self.create_bst(arr, start, mid - 1)
		root.right = self.create_bst(arr, mid + 1, end)
		return root

	def buildBalancedTree(self, root):
		arr = self.inorder(root)
		root = self.create_bst(arr, 0, len(arr) - 1)
		return root


class Solution:

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

	def bst(self, st, lst):
		if st > lst:
			return None
		mid = (st + lst) // 2
		root = Node(self.l[mid])
		root.left = self.bst(st, mid - 1)
		root.right = self.bst(mid + 1, lst)
		return root

	def buildBalancedTree(self, root):
		self.l = []
		self.solve(root)
		st = 0
		n = len(self.l)
		lst = n - 1
		return self.bst(st, lst)


class Solution:

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

	def solve(self, start, end):
		if start > end:
			return
		mid = (start + end) // 2
		root = Node(self.res[mid])
		root.left = self.solve(start, mid - 1)
		root.right = self.solve(mid + 1, end)
		return root

	def buildBalancedTree(self, root):
		self.res = []
		self.inorder(root)
		start = 0
		end = len(self.res) - 1
		return self.solve(start, end)


class Solution:

	def buildBalancedTree(self, root):

		def inord(node=root, res=[]):
			if node:
				inord(node.left)
				res += (node.data,)
				inord(node.right)
			return res

		def balance(lst=inord()):
			if lst:
				mid = len(lst) // 2
				(l, r) = (lst[:mid], lst[mid + 1:])
				(node, node.left, node.right) = (Node(lst[mid]), *map(balance, [l, r]))
				return node
		return balance()


import math

class Solution:

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

	def buildBalancedTree(self, root):
		output = []
		self.inorder(root, output)
		return self.build_from_inorder(output, 0, len(output) - 1)

	def build_from_inorder(self, inorder, l, r):
		if r <= l:
			return Node(inorder[r])
		mid = l + math.ceil((r - l) / 2)
		head = Node(inorder[mid])
		left = self.build_from_inorder(inorder, l, mid - 1)
		right = self.build_from_inorder(inorder, mid + 1, r)
		head.left = left
		head.right = right
		return head


class Solution:

	def buildBalancedTree(self, root):

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

		def insertbst(li, l, r):
			if l > r:
				return None
			mid = (l + r) // 2
			newroot = Node(li[mid])
			newroot.left = insertbst(li, l, mid - 1)
			newroot.right = insertbst(li, mid + 1, r)
			return newroot
		li = []
		inorder(root, li)
		return insertbst(li, 0, len(li) - 1)


class Solution:

	def buildBalancedTree(self, root):

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

		def build(res):
			n = len(res)
			if not n:
				return None
			mid = len(res) // 2
			root = Node(res[mid])
			root.left = build(res[:mid])
			root.right = build(res[mid + 1:])
			return root
		a = []
		inorder(root, a)
		return build(a)


class Solution:

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

	def bst(self, v: []):
		if len(v) <= 0:
			return None
		s = 0
		e = len(v) - 1
		mid = s + (e - s) // 2
		root = Node(v[mid])
		root.left = self.bst(v[s:mid])
		root.right = self.bst(v[mid + 1:])
		return root

	def buildBalancedTree(self, root):
		v = []
		self.sarr(root, v)
		s = 0
		e = len(v)
		return self.bst(v)


class Solution:

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

	def toBst(self, s, e, inorder):
		if s >= e:
			return None
		mid = (s + e) // 2
		root = Node(inorder[mid])
		root.left = self.toBst(s, mid, inorder)
		root.right = self.toBst(mid + 1, e, inorder)
		return root

	def buildBalancedTree(self, root):
		inorder = self.inorder(root, [])
		n = len(inorder)
		return self.toBst(0, n, inorder)


class Solution:

	def buildBalancedTree(self, root):

		def inOrder(root, ans):
			if root is None:
				return
			inOrder(root.left, ans)
			ans.append(root)
			inOrder(root.right, ans)

		def inOrderToBst(start, end, ans):
			if start > end:
				return None
			mid = (start + end) // 2
			root = Node(ans[mid])
			root.left = inOrderToBst(start, mid - 1, ans)
			root.right = inOrderToBst(mid + 1, end, ans)
			return root
		ans = []
		inOrder(root, ans)
		return inOrderToBst(0, len(ans) - 1, ans)


class Solution:

	def buildBalancedTree(self, root):

		def ino(root, l):
			if root:
				ino(root.left, l)
				l.append(root.data)
				ino(root.right, l)
			return len(l)

		def build(l, s, e):
			if s > e:
				return None
			m = (s + e) // 2
			node = Node(l[m])
			node.left = build(l, s, m - 1)
			node.right = build(l, m + 1, e)
			return node
		l = []
		n = ino(root, l)
		return build(l, 0, n - 1)


class Solution:

	def buildBalancedTree(self, root):
		in_order_arr = []
		self.in_order_util(root, in_order_arr)
		return self.create_bst_from_in_order(in_order_arr)

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

	def create_bst_from_in_order(self, in_order_arr: []):
		if len(in_order_arr) <= 0:
			return None
		start = 0
		end = len(in_order_arr) - 1
		middle = start + (end - start) // 2
		root = Node(in_order_arr[middle])
		root.left = self.create_bst_from_in_order(in_order_arr[start:middle])
		root.right = self.create_bst_from_in_order(in_order_arr[middle + 1:])
		return root


class Solution:

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

	def arr_to_bst(self, arr):
		if not arr:
			return
		mid = len(arr) // 2
		root = Node(arr[mid])
		root.left = self.arr_to_bst(arr[:mid])
		root.right = self.arr_to_bst(arr[mid + 1:])
		return root

	def buildBalancedTree(self, root):
		arr = []
		self.in_order(root, arr)
		out = self.arr_to_bst(arr)
		return out


class Solution:

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

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

		def maketree(l, r):
			if r < l:
				return None
			mid = l + (r - l + 1) // 2
			node = Node(inorder[mid])
			node.left = maketree(l, mid - 1)
			node.right = maketree(mid + 1, r)
			return node
		return maketree(0, len(inorder) - 1)


class Solution:

	def buildBalancedTree(self, root):

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

		def construct(ans, a, b):
			if a > b:
				return None
			mid = (a + b) // 2
			root = Node(ans[mid])
			root.left = construct(ans, a, mid - 1)
			root.right = construct(ans, mid + 1, b)
			return root
		return construct(ans, 0, len(ans) - 1)


class Solution:

	def buildBalancedTree(self, root):
		res = []
		res = self.convert(root, res)
		res.sort()
		return self.BBST(res)

	def BBST(self, res):
		if not res:
			return None
		mid = len(res) // 2
		root = Node(res[mid])
		root.left = self.BBST(res[:mid])
		root.right = self.BBST(res[mid + 1:])
		return root

	def convert(self, root, res):
		if not root:
			return 0
		res.append(root.data)
		self.convert(root.left, res)
		self.convert(root.right, res)
		return res


class Solution:

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

	def buildtree(self, li, si, ei):
		if si > ei:
			return None
		mid = si + (ei - si) // 2
		root = li[mid]
		root.left = self.buildtree(li, si, mid - 1)
		root.right = self.buildtree(li, mid + 1, ei)
		return root

	def buildBalancedTree(self, root):
		li = []
		li = self.inorderbst(root, li)
		return self.buildtree(li, 0, len(li) - 1)


class Solution:

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

	def inordertoBST(self, s, e, inorderVal):
		if s > e:
			return None
		mid = (s + e) // 2
		root = Node(inorderVal[mid])
		root.left = self.inordertoBST(s, mid - 1, inorderVal)
		root.right = self.inordertoBST(mid + 1, e, inorderVal)
		return root

	def buildBalancedTree(self, root):
		inorderVal = []
		self.inorder(root, inorderVal)
		return self.inordertoBST(0, len(inorderVal) - 1, inorderVal)


def store(root, nodes):
	if not root:
		return
	store(root.left, nodes)
	nodes.append(root)
	store(root.right, nodes)

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

class Solution:

	def buildBalancedTree(self, root):
		nodes = []
		store(root, nodes)
		n = len(nodes)
		return BTU(nodes, 0, n - 1)


class Solution:

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

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

	def buildBalancedTree(self, root):
		inorder = []
		self.inorder_traversal(root, inorder)
		root = self.create_bst(inorder, 0, len(inorder) - 1)
		return root


class Solution:

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

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

	def buildBalancedTree(self, root):
		nodes = []
		self.storeBstNodes(root, nodes)
		n = len(nodes)
		return self.buildTree(nodes, 0, n - 1)


class Solution:

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

	def solve(self, start, end, a):
		if start > end:
			return
		mid = (start + end) // 2
		root = Node(a[mid])
		root.left = self.solve(start, mid - 1, a)
		root.right = self.solve(mid + 1, end, a)
		return root

	def buildBalancedTree(self, root):
		a = self.inorder(root, [])
		start = 0
		end = len(a) - 1
		return self.solve(start, end, a)


class Solution:

	def buildBalancedTree(self, root):
		arr = self.inOrderTraversal(root)
		i = len(arr) // 2
		root = Node(arr[i])
		if arr[:i]:
			root.left = Node(0)
			self.helper(arr[:i], root.left)
		if arr[i + 1:]:
			root.right = Node(0)
			self.helper(arr[i + 1:], root.right)
		return root

	def inOrderTraversal(self, root):
		if not root:
			return []
		output = self.inOrderTraversal(root.left)
		output.append(root.data)
		return output + self.inOrderTraversal(root.right)

	def helper(self, arr, root):
		i = len(arr) // 2
		root.data = arr[i]
		if arr[:i]:
			root.left = Node(0)
			self.helper(arr[:i], root.left)
		if arr[i + 1:]:
			root.right = Node(0)
			self.helper(arr[i + 1:], root.right)
		return


class Solution:

	def creatBst(self, start, end, arr):
		if start > end:
			return None
		mid = (start + end) // 2
		root = Node(arr[mid])
		root.left = self.creatBst(start, mid - 1, arr)
		root.right = self.creatBst(mid + 1, end, arr)
		return root

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

	def buildBalancedTree(self, root):
		arr = []
		self.solve(root, arr)
		start = 0
		end = len(arr) - 1
		ans = self.creatBst(start, end, arr)
		return ans


class Solution:

	def buildBalancedTree(self, root):
		a = []

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

		def man(a):
			if a == []:
				return None
			roo = Node(a[len(a) // 2])
			roo.left = man(a[:len(a) // 2])
			roo.right = man(a[len(a) // 2 + 1:])
			return roo
		return man(a)


class Solution:

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

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

		def dfs(l, h):
			if l > h:
				return None
			mid = (l + h) // 2
			root1 = Node(arr[mid])
			root1.left = dfs(l, mid - 1)
			root1.right = dfs(mid + 1, h)
			return root1
		inorder(root)
		arr.sort()
		return dfs(0, len(arr) - 1)


class Solution:

	def inorderToBst(self, s, e, In):
		if s > e:
			return None
		mid = s + (e - s) // 2
		root = Node(In[mid])
		root.left = self.inorderToBst(s, mid - 1, In)
		root.right = self.inorderToBst(mid + 1, e, In)
		return root

	def buildBalancedTree(self, root):
		In = []

		def inorder(root, In):
			if root == None:
				return
			inorder(root.left, In)
			In.append(root.data)
			inorder(root.right, In)
		inorder(root, In)
		return self.inorderToBst(0, len(In) - 1, In)


class Solution:

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

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

		def bst(l):
			if len(l) == 0:
				return
			mid = len(l) // 2
			root = Node(l[mid])
			root.left = bst(l[:mid])
			root.right = bst(l[mid + 1:])
			return root
		inorder(root)
		return bst(l)


class Solution:
	inorder_list = []

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

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

	def frominorderlist(self, sorted_list):
		if len(sorted_list) == 0:
			return None
		mid = len(sorted_list) // 2
		root_node = sorted_list[mid]
		root_node.left = self.frominorderlist(sorted_list[:mid])
		root_node.right = self.frominorderlist(sorted_list[mid + 1:])
		return root_node

	def buildBalancedTree(self, root):
		self.inorder(root)
		temp = self.inorder_list.copy()
		self.inorder_list = []
		return self.frominorderlist(temp)


class Solution:

	def buildBalancedTree(self, root):
		l = self.solve(root, [])
		return self.tree(l)

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

	def tree(self, l):
		if len(l) == 0:
			return None
		if len(l) == 1:
			return Node(l[0])
		m = len(l) // 2
		root = Node(l[m])
		root.left = self.tree(l[:m])
		root.right = self.tree(l[m + 1:])
		return root


class Solution:

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

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

	def buildBalancedTree(self, root):
		inorderArr = []
		self.inorder(root, inorderArr)
		left = 0
		right = len(inorderArr) - 1
		return self.build(inorderArr, left, right)


class Solution:

	def buildBalancedTree(self, root):
		sortedNodes = []

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

		def buildBST(i, j):
			if i > j:
				return None
			if i == j:
				return Node(sortedNodes[i])
			mid = (i + j) // 2
			root = Node(sortedNodes[mid])
			root.left = buildBST(i, mid - 1)
			root.right = buildBST(mid + 1, j)
			return root
		inorder(root)
		newRoot = buildBST(0, len(sortedNodes) - 1)
		return newRoot


class Solution:

	def buildBalancedTree(self, root):
		list = []
		inorder(root, list)
		return makeBalanceTree(list, 0, len(list) - 1)

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

def makeBalanceTree(list, low, high):
	if low > high:
		return None
	mid = (low + high) // 2
	node = Node(list[mid])
	node.left = makeBalanceTree(list, low, mid - 1)
	node.right = makeBalanceTree(list, mid + 1, high)
	return node


class Solution:

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

	def recur(self, arr):
		if len(arr) == 0:
			return None
		mid = len(arr) // 2
		root = Node(arr[mid])
		root.left = self.recur(arr[:mid])
		root.right = self.recur(arr[mid + 1:])
		return root

	def buildBalancedTree(self, root):
		self.list = []
		self.val(root)
		root = self.recur(self.list)
		return root


class Solution:

	def inOrder(self, root, ls):
		if not root:
			return
		self.inOrder(root.left, ls)
		ls.append(root.data)
		self.inOrder(root.right, ls)

	def lsToBst(self, ls, st, end):
		if st > end:
			return None
		mid = (st + end) // 2
		root = Node(ls[mid])
		root.left = self.lsToBst(ls, st, mid - 1)
		root.right = self.lsToBst(ls, mid + 1, end)
		return root

	def buildBalancedTree(self, root):
		ls = []
		self.inOrder(root, ls)
		n = len(ls)
		return self.lsToBst(ls, 0, n - 1)


class Solution:

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

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

		def build(array):
			if len(array) == 0:
				return
			l = 0
			h = len(array)
			mid = l + h >> 1
			root = Node(array[mid])
			root.left = build(array[:mid])
			root.right = build(array[mid + 1:])
			return root
		inorder(root)
		return build(arr)


def createBalancedBST(arr, l, r):
	if l > r:
		return None
	m = (l + r) // 2
	ptr = Node(arr[m])
	ptr.left = createBalancedBST(arr, l, m - 1)
	ptr.right = createBalancedBST(arr, m + 1, r)
	return ptr

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

class Solution:

	def buildBalancedTree(self, root):
		arr = inOrder(root)
		return createBalancedBST(arr, 0, len(arr) - 1)


class Solution:

	def buildBalancedTree(self, root):
		self.l = []

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

		def func(arr):
			if not arr:
				return
			mid = len(arr) // 2
			root = Node(arr[mid])
			root.left = func(arr[:mid])
			root.right = func(arr[mid + 1:])
			return root
		inorder(root)
		return func(self.l)


class Solution:

	def buildBalancedTree(self, root):
		res = []
		self.in_order_traversal(root, res)
		_new_root = self._bbst(res, 0, len(res) - 1)
		return _new_root

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

	def _bbst(self, res, low, high):
		if low > high:
			return None
		mid = (low + high) // 2
		root = Node(res[mid])
		root.left = self._bbst(res, low, mid - 1)
		root.right = self._bbst(res, mid + 1, high)
		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 build(self, ans):
		if not ans:
			return
		else:
			mid = len(ans) // 2
			root = Node(ans[mid])
			root.left = self.build(ans[:mid])
			root.right = self.build(ans[mid + 1:])
			return root

	def buildBalancedTree(self, root):
		ans = []
		self.inorder(root, ans)
		return self.build(ans)


class Solution:

	def buildBalancedTree(self, root):
		preorder = []

		def doPreorder(node):
			nonlocal preorder
			if node:
				doPreorder(node.left)
				preorder.append(node)
				doPreorder(node.right)
				node.left = node.right = None
		doPreorder(root)

		def convertToBST(s, e):
			nonlocal preorder
			if e < s:
				return None
			mid = (s + e) // 2
			node = preorder[mid]
			node.left = convertToBST(s, mid - 1)
			node.right = convertToBST(mid + 1, e)
			return node
		return convertToBST(0, len(preorder) - 1)


class Solution:

	def buildBalancedTree(self, root):
		keys = []

		def inOrder(root, keys):
			if root is None:
				return
			inOrder(root.left, keys)
			keys.append(root.data)
			inOrder(root.right, keys)
		inOrder(root, keys)

		def buildTree(keys, start, end):
			if end < start:
				return None
			mid = (start + end) // 2
			root = Node(keys[mid])
			root.left = buildTree(keys, start, mid - 1)
			root.right = buildTree(keys, mid + 1, end)
			return root
		return buildTree(keys, 0, len(keys) - 1)


class Solution:

	def buildBalancedTree(self, root):

		def build(arr):
			if not arr:
				return
			mid = len(arr) // 2
			root = Node(arr[mid])
			root.left = build(arr[:mid])
			root.right = build(arr[mid + 1:])
			return root

		def func(root, li):
			if root is None:
				return
			func(root.left, li)
			li.append(root.data)
			func(root.right, li)
		li = []
		func(root, li)
		return build(li)


class Solution:

	def buildBalancedTree(self, root):
		a = []

		def innorder(root):
			if not root:
				return
			innorder(root.left)
			a.append(root.data)
			innorder(root.right)

		def tree(arr):
			if not arr:
				return
			mid = len(arr) // 2
			root = Node(arr[mid])
			root.left = tree(arr[:mid])
			root.right = tree(arr[mid + 1:])
			return root
		innorder(root)
		b = tree(a)
		return b


class Solution:

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

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

		def tree(arr):
			if not arr:
				return
			if len(arr) == 1:
				return Node(arr[0])
			mid = len(arr) // 2
			node = Node(arr[mid])
			node.left = tree(arr[:mid])
			node.right = tree(arr[mid + 1:])
			return node
		dfs(root)
		head = tree(arr)
		return head


class Solution:

	def buildBalancedTree(self, root):

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

		def solve(temp):
			if not temp:
				return None
			mid = len(temp) // 2
			node = Node(temp[mid])
			node.left = solve(temp[:mid])
			node.right = solve(temp[mid + 1:])
			return node
		return solve(temp)


class Solution:

	def buildBalancedTree(self, root):
		values = list(self._inorder(root))
		return self._build_balanced_tree(values)

	def _build_balanced_tree(self, values, root=None):
		if len(values) != 0:
			core_value = values[len(values) // 2]
			left_values = [v for v in values if v < core_value]
			right_values = [v for v in values if v > core_value]
			root = self._insert(root, core_value)
			self._build_balanced_tree(left_values, root)
			self._build_balanced_tree(right_values, root)
		return root

	def _inorder(self, root):
		if root:
			yield from self._inorder(root.left)
			yield root.data
			yield from self._inorder(root.right)

	def _insert(self, root, new_value):
		if root is None:
			return Node(new_value)
		elif root.data == new_value:
			return root
		elif root.data < new_value:
			root.right = self._insert(root.right, new_value)
		else:
			root.left = self._insert(root.left, new_value)
		return root


class Solution:

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

		def dfs(root):
			if root == None:
				return
			dfs(root.left)
			res.append(root)
			dfs(root.right)
		dfs(root)
		if not res:
			return
		res.sort(key=lambda x: x.data)

		def dfs2(res):
			if len(res) == 0:
				return
			mid = (len(res) - 1) // 2
			root = res[mid]
			L = dfs2(res[:mid])
			R = dfs2(res[mid + 1:])
			root.left = L
			root.right = R
			return root
		return dfs2(res)


class Solution:

	def buildBalancedTree(self, root):
		a = []

		def ino(x):
			if x:
				ino(x.left)
				a.append(x.data)
				ino(x.right)
		ino(root)

		def atb(p, q, r):
			if p > q:
				return None
			m = (p + q) // 2
			n = Node(r[m])
			n.left = atb(p, m - 1, r)
			n.right = atb(m + 1, q, r)
			return n
		return atb(0, len(a) - 1, a)


class Solution:

	def buildBalancedTree(self, root):
		inord = []

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

		def build(arr):
			if not arr:
				return None
			mid = len(arr) // 2
			root = Node(inord[mid])
			root.left = build(arr[:mid])
			root.right = build(arr[mid + 1:])
			return root
		return build(inord)


class Solution:

	def traverse(self, root, order):
		if root.left:
			self.traverse(root.left, order)
		order.append(root.data)
		if root.right:
			self.traverse(root.right, order)

	def build(self, order):
		if not order:
			return None
		new_root = Node(order[len(order) // 2])
		left = order[:len(order) // 2]
		right = order[len(order) // 2 + 1:]
		new_root.left = self.build(left)
		new_root.right = self.build(right)
		return new_root

	def buildBalancedTree(self, root):
		order = []
		self.traverse(root, order)
		return self.build(order)


def pushTreeNodes(root, nodes):
	if root is None:
		return
	pushTreeNodes(root.left, nodes)
	nodes.append(root)
	pushTreeNodes(root.right, nodes)

def buildBalancedBST(nodes, start, end):
	if start > end:
		return None
	mid = (start + end) // 2
	root = nodes[mid]
	root.left = buildBalancedBST(nodes, start, mid - 1)
	root.right = buildBalancedBST(nodes, mid + 1, end)
	return root

def constructBalancedBST(root):
	nodes = []
	pushTreeNodes(root, nodes)
	return buildBalancedBST(nodes, 0, len(nodes) - 1)

class Solution:

	def buildBalancedTree(self, root):
		return constructBalancedBST(root)


class Solution:

	def buildBalancedTree(self, root):
		store = []

		def inOrder(root):
			if root is None:
				return
			inOrder(root.left)
			store.append(root.data)
			inOrder(root.right)
		inOrder(root)

		def buildTree(store):
			n = len(store)
			if n == 0:
				return
			mid = n // 2
			root = Node(store[mid])
			root.left = buildTree(store[:mid])
			root.right = buildTree(store[mid + 1:])
			return root
		return buildTree(store)


class Solution:

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

		def inorder(root, l):
			if root.left:
				inorder(root.left, l)
			l.append(root.data)
			if root.right:
				inorder(root.right, l)
			return
		inorder(root, l)
		e = len(l)

		def balBst(l, s, e):
			if s > e:
				return None
			mid = (s + e) // 2
			node = Node(l[mid])
			node.left = balBst(l, s, mid - 1)
			node.right = balBst(l, mid + 1, e)
			return node
		newRoot = balBst(l, 0, e - 1)
		return newRoot


class Solution:

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

	def arrToTree(self, arr, start, end, real_len):
		if start > end:
			return None
		midPoint = (end + start) // 2
		node = arr[midPoint]
		node.left = self.arrToTree(arr, start, midPoint - 1, real_len)
		node.right = self.arrToTree(arr, midPoint + 1, end, real_len)
		return node

	def buildBalancedTree(self, root):
		arr = []
		self.makeArray(root, arr)
		result = self.arrToTree(arr, 0, len(arr) - 1, len(arr) - 1)
		return result


class Solution:

	def buildBalancedTree(self, root):
		inorder = []
		self.inorder(root, inorder)
		return self.helper(0, len(inorder) - 1, inorder)

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

	def helper(self, s, e, inorder):
		if s > e:
			return None
		mid = (s + e) // 2
		root = Node(inorder[mid])
		root.left = self.helper(s, mid - 1, inorder)
		root.right = self.helper(mid + 1, e, inorder)
		return root


class BinaryTreeNode:

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

class Solution:

	def buildBalancedTree(self, root):

		def inorder(root):
			if root is None:
				return
			inorder(root.left)
			lst.append(root.data)
			inorder(root.right)
		lst = []
		inorder(root)

		def inorderBst(lst):
			n = len(lst)
			if lst is None or n <= 0:
				return None
			rootdata = (n - 1) // 2
			root = BinaryTreeNode(lst[rootdata])
			root.left = inorderBst(lst[:rootdata])
			root.right = inorderBst(lst[rootdata + 1:])
			return root
		return inorderBst(lst)


class Solution:

	def buildBalancedTree(self, root):
		v = []

		def inorder(root):
			if root is None:
				return
			inorder(root.left)
			v.append(root)
			inorder(root.right)

		def balance(left, right):
			if left > right:
				return None
			mid = (left + right) // 2
			root = v[mid]
			root.left = balance(left, mid - 1)
			root.right = balance(mid + 1, right)
			return root
		inorder(root)
		return balance(0, len(v) - 1)


class Solution:

	def buildBalancedTree(self, root):

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

		def main(arr, s, e):
			if s == e:
				return None
			pos = (s + e) // 2
			node = Node(arr[pos])
			node.left = main(arr, s, pos)
			node.right = main(arr, pos + 1, e)
			return node
		a = []
		bst_to_sorted_arr(root, a)
		return main(a, 0, len(a))


class Solution:

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

	def construct_tree(self, _in, start, end):
		if start > end:
			return None
		mid = start + end >> 1
		data = _in[mid]
		root = Node(data)
		root.left = self.construct_tree(_in, start, mid - 1)
		root.right = self.construct_tree(_in, mid + 1, end)
		return root

	def buildBalancedTree(self, root):
		_in = []
		self.inorder(root, _in)
		return self.construct_tree(_in, 0, len(_in) - 1)


class Solution:

	def buildBalancedTree(self, root):
		global arr
		arr = []
		self.inorder(root, arr)
		return self.build(arr)

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

	def build(self, arr):
		length = len(arr)
		if length == 0:
			return None
		i = length // 2
		root = Node(arr[i])
		root.left = self.build(arr[:i])
		root.right = self.build(arr[i + 1:])
		return root


class Solution:

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

	def bstmaker(self, A, L, R):
		if R < L:
			return None
		if R == L:
			return Node(A[L])
		mid = (L + R) // 2
		root = Node(A[mid])
		root.left = self.bstmaker(A, L, mid - 1)
		root.right = self.bstmaker(A, mid + 1, R)
		return root

	def buildBalancedTree(self, root):
		A = []
		self.inorder(root, A)
		L = 0
		R = len(A) - 1
		root = self.bstmaker(A, L, R)
		return root


class Solution:

	def buildBalancedTree(self, root):
		arr = self.inOrder(root)
		resp = self.solver(arr)
		return resp

	def solver(self, arr):
		n = len(arr)
		mid = n // 2
		if mid < n:
			resp = arr[mid]
			resp.left = self.solver(arr[:mid])
			resp.right = self.solver(arr[mid + 1:])
			return resp

	def inOrder(self, root):
		return self.inOrder(root.left) + [root] + self.inOrder(root.right) if root else []


class Solution:

	def buildBalancedTree(self, root):
		self.ans = []
		node = root

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

		def bst(l, r):
			if l > r:
				return None
			mid = (l + r) // 2
			root = Node(self.ans[mid])
			root.left = bst(l, mid - 1)
			root.right = bst(mid + 1, r)
			return root
		f(node)
		return bst(0, len(self.ans) - 1)


class Solution:

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

	def build(self, low, high):
		if low > high:
			return None
		mid = (low + high) // 2
		newNode = Node(self.arr[mid])
		newNode.left = self.build(low, mid - 1)
		newNode.right = self.build(mid + 1, high)
		return newNode

	def buildBalancedTree(self, root):
		self.arr = []
		self.traverse(root)
		return self.build(0, len(self.arr) - 1)


class Solution:

	def buildBalancedTree(self, root):

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

		def inToBST(s, e, in_):
			if s > e:
				return None
			mid = (s + e) // 2
			node = Node(in_[mid])
			node.left = inToBST(s, mid - 1, in_)
			node.right = inToBST(mid + 1, e, in_)
			return node
		in_ = []
		inorder(root, in_)
		newroot = inToBST(0, len(in_) - 1, in_)
		return newroot


class Solution:

	def ino(self, l, r):
		if r:
			self.ino(l, r.left)
			l.append(r)
			self.ino(l, r.right)

	def buildBalancedTree(self, root):
		l = []
		self.ino(l, root)
		n = len(l)
		for i in range(n):
			l[i].left = None
			l[i].right = None
			d = 2 * i + 1
			if d < n:
				l[i].left = l[d]
			if d + 1 < n:
				l[i].right = l[d + 1]
		return l[0]


class Solution:

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

	def maketree(self, lst, low, high):
		mid = (low + high) // 2
		root = Node(lst[mid])
		if low < mid:
			root.left = self.maketree(lst, low, mid - 1)
		if high > mid:
			root.right = self.maketree(lst, mid + 1, high)
		return root

	def buildBalancedTree(self, root):
		lst = []
		self.inorder(root, lst)
		return self.maketree(lst, 0, len(lst) - 1)


class Solution:

	def buildBalancedTree(self, root):
		arr = []
		inorder(root, arr)
		res = inorderToBST(0, len(arr) - 1, arr)
		return res

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

def inorderToBST(start, end, arr):
	if start > end:
		return None
	mid = (start + end) // 2
	root = Node(arr[mid])
	root.left = inorderToBST(start, mid - 1, arr)
	root.right = inorderToBST(mid + 1, end, arr)
	return root


class Solution:

	def buildBalancedTree(self, root):

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

		def f(arr):
			if not arr:
				return
			mid = len(arr) // 2
			root = Node(arr[mid])
			root.left = f(arr[:mid])
			root.right = f(arr[mid + 1:])
			return root
		return f(arr)


def ino(root):
	if root == None:
		return []
	ele = []
	ele += ino(root.left)
	ele += [root]
	ele += ino(root.right)
	return ele

def tob(data):
	if len(data) == 0:
		return None
	mid = len(data) // 2
	root = data[mid]
	root.left = tob(data[:mid])
	root.right = tob(data[mid + 1:])
	return root

class Solution:

	def buildBalancedTree(self, root):
		data = ino(root)
		return tob(data)


class Solution:

	def buildBalancedTree(self, root):

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

		def balbst(start, end, list1):
			if start > end:
				return
			mid = (start + end) // 2
			temp = Node(list1[mid])
			temp.left = balbst(start, mid - 1, list1)
			temp.right = balbst(mid + 1, end, list1)
			return temp
		list1 = []
		inorder(root, list1)
		return balbst(0, len(list1) - 1, list1)


class Solution:

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

		def test(root):
			if root is None:
				return
			test(root.left)
			res.append(root.data)
			test(root.right)
		test(root)

		def construct(node, start, end):
			if start > end:
				return
			mid = (start + end) // 2
			node = Node(res[mid])
			node.left = construct(node, start, mid - 1)
			node.right = construct(node, mid + 1, end)
			return node
		return construct(res, 0, len(res) - 1)