Given a sorted array. Convert it into a Height balanced Binary Search Tree (BST). Find the preorder traversal of height balanced BST. If there exist many such balanced BST consider the tree whose preorder is lexicographically smallest.
Height balanced BST means a binary tree in which the depth of the left subtree and the right subtree of every node never differ by more than 1.
Example 1:
Input: nums = {1, 2, 3, 4}
Output: {2, 1, 3, 4}
Explanation: 
The preorder traversal of the following 
BST formed is {2, 1, 3, 4}:
           2
         /   \
           1     3
               \
                4
 
Example 2:
Input: nums = {1,2,3,4,5,6,7}
Ouput: {4,2,1,3,6,5,7}
Explanation: 
The preorder traversal of the following
BST formed is {4,2,1,3,6,5,7} :
        4
       / \
      2   6
     / \  / \
    1   3 5  7
 
Your Task:
You don't need to read or print anything. Your task is to complete the function sortedArrayToBST() which takes the sorted array nums as input paramater and returns the preorder traversal of height balanced BST. If there exist many such balanced BST consider the tree whose preorder is lexicographically smallest.
Expected Time Complexity: O(n)
Expected Space Complexity: O(n)
Constraints:
1 ≤ |nums| ≤ 10^{4}
-10^{4} ≤ nums[i] ≤ 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Range queries

Starter code: class Solution:
	def sortedArrayToBST(self, nums):
	    # code here

Solutions:
class TreeNode:

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

def preOrder(root, ans):
	if not root:
		return
	ans.append(root.val)
	preOrder(root.left, ans)
	preOrder(root.right, ans)

def insert(root, val):
	if not root:
		root = TreeNode(val)
		return root
	if root.val > val:
		return insert(root.left, val)
	return insert(root.right, val)

def fun(root, nums, l, r):
	mid = (l + r) // 2
	root = insert(root, nums[mid])
	if mid != l:
		root.left = fun(root, nums, l, mid - 1)
	if mid != r:
		root.right = fun(root, nums, mid + 1, r)
	return root

class Solution:

	def sortedArrayToBST(self, nums):
		ans = []
		if len(nums) == 0:
			return ans
		root = fun(None, nums, 0, len(nums) - 1)
		preOrder(root, ans)
		return ans


class Solution:

	def sortedArrayToBST(self, nums):
		s = 0
		e = len(nums) - 1
		ans = []

		def solve(arr, s, e, ans):
			if s > e:
				return
			mid = (s + e) // 2
			ans.append(arr[mid])
			solve(arr, s, mid - 1, ans)
			solve(arr, mid + 1, e, ans)
		solve(nums, s, e, ans)
		return ans


class Solution:

	def sortedArrayToBST(self, nums):

		def arraytoBST(nums):
			if len(nums) == 0:
				return []
			if len(nums) == 1:
				return [nums[0]]
			mid = (len(nums) - 1) // 2
			left = nums[:mid]
			right = nums[mid + 1:]
			return [nums[mid]] + arraytoBST(left) + arraytoBST(right)
		return arraytoBST(nums)


class Solution:

	def sortedArrayToBST(self, nums):

		def sortedArrayToBST(nums, start, last):
			nonlocal ans
			if start > last:
				return
			mid = (start + last) // 2
			ans.append(nums[mid])
			sortedArrayToBST(nums, start, mid - 1)
			sortedArrayToBST(nums, mid + 1, last)
		ans = []
		sortedArrayToBST(nums, 0, len(nums) - 1)
		return ans


class TreeNode:

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

class Solution:

	def sortedArrayToBST(self, nums):

		def sortedArrayToBST(nums, start, last):
			nonlocal ans
			if start > last:
				return
			mid = (start + last) // 2
			ans.append(nums[mid])
			sortedArrayToBST(nums, start, mid - 1)
			sortedArrayToBST(nums, mid + 1, last)
		ans = []
		sortedArrayToBST(nums, 0, len(nums) - 1)
		return ans


class Solution:

	def solve(self, nums, st, lst):
		if st > lst:
			return
		mid = (st + lst) // 2
		self.ans.append(nums[mid])
		self.solve(nums, st, mid - 1)
		self.solve(nums, mid + 1, lst)

	def sortedArrayToBST(self, nums):
		st = 0
		lst = len(nums) - 1
		self.ans = []
		self.solve(nums, st, lst)
		return self.ans


class Node:

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

class Solution:

	def arr2Bst(self, nums, s, e):
		if s > e:
			return
		mid = s + (e - s) // 2
		self.ans.append(nums[mid])
		self.arr2Bst(nums, s, mid - 1)
		self.arr2Bst(nums, mid + 1, e)

	def sortedArrayToBST(self, nums):
		(s, e) = (0, len(nums) - 1)
		self.ans = []
		self.arr2Bst(nums, s, e)
		return self.ans


class TreeNode:

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

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

def insert(root, val):
	if root is None:
		root = TreeNode(val)
		return root
	if root.val > val:
		return insert(root.left, val)
	else:
		return insert(root.right, val)

def fun(root, nums, l, r):
	mid = int((l + r) / 2)
	root = insert(root, nums[mid])
	if mid != l:
		root.left = fun(root, nums, l, mid - 1)
	if mid != r:
		root.right = fun(root, nums, mid + 1, r)
	return root

class Solution:

	def sortedArrayToBST(self, nums):
		ans = []
		if len(nums) == 0:
			return ans
		root = fun(None, nums, 0, len(nums) - 1)
		preorder(root, ans)
		return ans


class Solution:

	def sortedArrayToBST(self, nums):
		if len(nums) == 0:
			return []
		mid = (len(nums) - 1) // 2
		ans = [nums[mid]]
		left = self.sortedArrayToBST(nums[0:mid])
		right = self.sortedArrayToBST(nums[mid + 1:])
		ans.extend(left)
		ans.extend(right)
		return ans


class Solution:

	def sortedArrayToBST(self, nums):
		l = []

		def func(nums):
			len_ = len(nums)
			if len_ > 0:
				mid = len_ // 2 if len_ % 2 == 1 else len_ // 2 - 1
				print(nums[mid], end=' ')
				func(nums[:mid])
				func(nums[mid + 1:])
			return None
		func(nums)
		return l


class Node:

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

class Solution:

	def sortedArrayToBST(self, nums):

		def ans(arr):
			if len(arr) == 0:
				return
			mid = (len(arr) - 1) // 2
			pre.append(arr[mid])
			ans(arr[:mid])
			ans(arr[mid + 1:])
			return

		def preorder(root):
			if root:
				pre.append(root.data)
				preorder(root.left)
				preorder(root.right)
		pre = []
		ans(nums)
		return pre


class Solution:

	def sortedArrayToBST(self, nums):
		ans = []

		def dfs(nums, l, r):
			if l > r:
				return
			mid = (l + r) // 2
			ans.append(nums[mid])
			dfs(nums, l, mid - 1)
			dfs(nums, mid + 1, r)
		dfs(nums, 0, len(nums) - 1)
		return ans


class Solution:

	def sortedArrayToBST(self, nums):
		hi = len(nums) - 1

		def recurse(lo, hi):
			if lo > hi:
				return []
			if lo == hi:
				return [nums[lo]]
			mid = (lo + hi) // 2
			return [nums[mid]] + recurse(lo, mid - 1) + recurse(mid + 1, hi)
		return recurse(0, hi)


class TreeNode:

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

class Solution:

	def sortedArrayToBST(self, nums):
		root = self.helper(nums)
		return self.preOrder(root)

	def helper(self, nums):
		if not nums:
			return
		mid = 0 + len(nums) - 1 >> 1
		head = TreeNode(nums[mid])
		head.left = self.helper(nums[:mid])
		head.right = self.helper(nums[mid + 1:])
		return head

	def preOrder(self, root):
		(stack, res) = ([root], [])
		while stack:
			cur = stack.pop()
			res.append(cur.data)
			if cur.right:
				stack.append(cur.right)
			if cur.left:
				stack.append(cur.left)
		return res


class Solution:

	def sortedArrayToBST(self, nums):
		if not nums:
			return []
		mid = 0 + len(nums) - 1 >> 1
		return [nums[mid]] + self.sortedArrayToBST(nums[:mid]) + self.sortedArrayToBST(nums[mid + 1:])


class Solution:

	def sortedArrayToBST(self, nums):
		res = []
		self.helper(nums, 0, len(nums) - 1, res)
		return res

	def helper(self, nums, l, r, res):
		if l <= r:
			mid = l + r >> 1
			res.append(nums[mid])
			self.helper(nums, l, mid - 1, res)
			self.helper(nums, mid + 1, r, res)


class Solution:

	def sortedArrayToBST(self, nums):

		def solve(self, nums, left, right):
			if left > right:
				return
			mid = (left + right) // 2
			self.ans.append(nums[mid])
			solve(self, nums, left, mid - 1)
			solve(self, nums, mid + 1, right)
		self.ans = []
		solve(self, nums, 0, len(nums) - 1)
		return self.ans


class Solution:

	def sortedArrayToBST(self, nums):
		ans = []

		def bld(nums, ans):
			n = len(nums)
			if n == 0:
				return
			if n % 2:
				k = n // 2
			else:
				k = n // 2 - 1
			root = nums[k]
			ans.append(root)
			bld(nums[:k], ans)
			bld(nums[k + 1:], ans)
		bld(nums, ans)
		return ans


class Solution:

	def sortedArrayToBST(self, nums):
		preorder = []
		self.helper(nums, 0, len(nums) - 1, preorder)
		return preorder

	def helper(self, nums, left, right, preorder):
		if left <= right:
			mid = left + (right - left) // 2
			preorder.append(nums[mid])
			self.helper(nums, left, mid - 1, preorder)
			self.helper(nums, mid + 1, right, preorder)


class Solution:

	def sortedArrayToBST(self, nums):
		if len(nums) == 1 or len(nums) == 0:
			return nums
		if len(nums) % 2 == 0:
			return [nums[len(nums) // 2 - 1]] + self.sortedArrayToBST(nums[:len(nums) // 2 - 1]) + self.sortedArrayToBST(nums[len(nums) // 2:])
		else:
			return [nums[len(nums) // 2]] + self.sortedArrayToBST(nums[:len(nums) // 2]) + self.sortedArrayToBST(nums[len(nums) // 2 + 1:])


class Solution:

	def sortedArrayToBST(self, nums: list) -> list:
		result = []
		if len(nums) != 0:
			self._sortedArrayToBST(nums, result, 0, len(nums) - 1)
		return result

	def _sortedArrayToBST(self, nums: list, result: list, start: int, end: int) -> None:
		if start > end:
			return
		m = (start + end) // 2
		result.append(nums[m])
		self._sortedArrayToBST(nums, result, start, m - 1)
		self._sortedArrayToBST(nums, result, m + 1, end)


import math

class Solution:

	def sortedArrayToBST(self, nums):
		res = []

		def rec(nums):
			if len(nums) == 0:
				return
			if len(nums) == 1:
				res.append(nums[0])
				return
			m = math.ceil(len(nums) / 2) - 1
			res.append(nums[m])
			rec(nums[:m])
			if m + 1 < len(nums):
				rec(nums[m + 1:])
		rec(nums)
		return res


class Solution:

	def sortedArrayToBST(self, nums):
		res = []

		def preOrder(arr, low, high, res):
			if low > high:
				return
			mid = (low + high) // 2
			res.append(arr[mid])
			preOrder(arr, low, mid - 1, res)
			preOrder(arr, mid + 1, high, res)
		preOrder(nums, 0, len(nums) - 1, res)
		return res


class Solution:

	def sortedArrayToBST(self, nums):
		low = 0
		high = len(nums) - 1
		ans = []

		def ToBst(nums, ans, low, high):
			if low > high:
				return
			mid = (low + high) // 2
			ans.append(nums[mid])
			ToBst(nums, ans, low, mid - 1)
			ToBst(nums, ans, mid + 1, high)
		ToBst(nums, ans, low, high)
		return ans


class Solution:

	def sortedArrayToBST(self, nums):
		return Solution().result(nums, [])

	def result(self, nums, arr):
		if len(nums) == 0:
			return arr
		size = len(nums) - 1
		mid = size // 2
		arr.append(nums[mid])
		Solution().result(nums[:mid], arr)
		Solution().result(nums[mid + 1:], arr)
		return arr


class Solution:

	def sortedArrayToBST(self, nums):
		resultPreorder = []
		self.toBST(nums, resultPreorder, 0, len(nums) - 1)
		return resultPreorder

	def toBST(self, nums, list, start, end):
		if end < start:
			return None
		mid = (start + end) // 2
		list.append(nums[mid])
		self.toBST(nums, list, start, mid - 1)
		self.toBST(nums, list, mid + 1, end)


class Solution:

	def sortedArrayToBST(self, nums):
		res = []
		self.sortedArrayToBSTHelper(res, 0, len(nums) - 1, nums)
		return res

	def sortedArrayToBSTHelper(self, res, left, right, nums):
		if left > right:
			return None
		mid = (left + right) // 2
		res.append(nums[mid])
		self.sortedArrayToBSTHelper(res, left, mid - 1, nums)
		self.sortedArrayToBSTHelper(res, mid + 1, right, nums)


class Solution:

	def findd(self, nums, start, end):
		if start > end:
			return
		mid = (start + end) // 2
		self.ans.append(nums[mid])
		self.findd(nums, start, mid - 1)
		self.findd(nums, mid + 1, end)

	def sortedArrayToBST(self, nums):
		start = 0
		end = len(nums) - 1
		self.ans = []
		self.findd(nums, start, end)
		return self.ans


class Solution:

	def __init__(self):
		self.n = []
		self.nums = None

	def sortedArrayToBST(self, nums):
		self.nums = nums
		self.createBst(0, len(nums) - 1)
		return self.n

	def createBst(self, l, r):
		if l == r:
			self.n.append(nums[l])
			return
		elif l > r:
			return
		mid = int((l + r) / 2)
		self.n.append(nums[mid])
		self.createBst(l, mid - 1)
		self.createBst(mid + 1, r)


class Solution:

	def sortedArrayToBST(self, nums):

		def build(nums, s, e, a):
			if s > e:
				return
			m = (s + e) // 2
			a.append(nums[m])
			build(nums, s, m - 1, a)
			build(nums, m + 1, e, a)
			return a
		a = []
		build(nums, 0, len(nums) - 1, a)
		return a


import math

class Solution:

	def sortedArrayToBST(self, nums):
		return self.to_preorder(nums, 0, len(nums) - 1)

	def to_preorder(self, nums, l, r):
		if l > r:
			return []
		elif l == r:
			return [nums[l]]
		root_index = l + math.floor((r - l) / 2)
		output_left = self.to_preorder(nums, l, root_index - 1)
		output_right = self.to_preorder(nums, root_index + 1, r)
		return [nums[root_index]] + output_left + output_right


class Solution:

	def bina(self, s, e, l, nums):
		if s > e:
			return
		else:
			mid = s + (e - s) // 2
			l.append(nums[mid])
			self.bina(s, mid - 1, l, nums)
			self.bina(mid + 1, e, l, nums)

	def sortedArrayToBST(self, nums):
		l = []
		self.bina(0, len(nums) - 1, l, nums)
		return l


class Solution:

	def binary_search(self, nums, st, lst):
		if st > lst:
			return
		mid = (st + lst) // 2
		self.empty_list.append(nums[mid])
		self.binary_search(nums, st, mid - 1)
		self.binary_search(nums, mid + 1, lst)

	def sortedArrayToBST(self, nums):
		st = 0
		lst = len(nums) - 1
		self.empty_list = []
		self.binary_search(nums, st, lst)
		return self.empty_list


class Node:

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

class Solution:

	def sortedArrayToBST(self, nums):
		result = []
		root = self.BST(nums, 0, len(nums) - 1)
		self.PreOrder(root, result)
		return result

	def BST(self, nums, left, right):
		if left > right:
			return None
		mid = (left + right) // 2
		node = Node(nums[mid])
		node.left = self.BST(nums, left, mid - 1)
		node.right = self.BST(nums, mid + 1, right)
		return node

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


class Solution:

	def sortedArrayToBST(self, arr):
		low = 0
		high = len(arr) - 1
		ans = []

		def solve(arr, ans, low, high):
			if low > high:
				return
			mid = (low + high) // 2
			ans.append(arr[mid])
			solve(arr, ans, low, mid - 1)
			solve(arr, ans, mid + 1, high)
		solve(arr, ans, low, high)
		return ans


class Solution:

	def sortedArrayToBST(self, nums):
		sol = []

		def cal(l, h):
			if l > h:
				return
			mid = (l + h) // 2
			sol.append(nums[mid])
			cal(l, mid - 1)
			cal(mid + 1, h)
		cal(0, len(nums) - 1)
		return sol


class Node:

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

class Solution:

	def Preorder(self, root, ans):
		if root == None:
			return
		ans[0].append(root.data)
		self.Preorder(root.left, ans)
		self.Preorder(root.right, ans)

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

	def sortedArrayToBST(self, nums):
		root = self.ArraytoBST(nums, 0, len(nums) - 1)
		ans = [[]]
		self.Preorder(root, ans)
		return ans[0]


class Solution:

	def sortedArrayToBST(self, nums):
		(l, h) = (0, len(nums) - 1)
		ans = []

		def preorder(nums, ans, l, h):
			if l > h:
				return
			mid = (l + h) // 2
			ans.append(nums[mid])
			preorder(nums, ans, l, mid - 1)
			preorder(nums, ans, mid + 1, h)
		preorder(nums, ans, l, h)
		return ans


class Solution:

	def sortedArrayToBST(self, nums):
		v = []
		self.helper(nums, 0, len(nums) - 1, v)
		return v

	def helper(self, nums, s, e, v):
		if s > e:
			return
		mid = (s + e) // 2
		v.append(nums[mid])
		self.helper(nums, s, mid - 1, v)
		self.helper(nums, mid + 1, e, v)


class Solution:

	def sortedArrayToBST(self, nums):
		beg = 0
		end = len(nums) - 1
		ans = []

		def Convert(nums, ans, beg, end):
			if beg > end:
				return
			mid = (beg + end) // 2
			ans.append(nums[mid])
			Convert(nums, ans, beg, mid - 1)
			Convert(nums, ans, mid + 1, end)
		Convert(nums, ans, beg, end)
		return ans


class Node:

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

class Solution:

	def convert(self, nums):
		if len(nums) == 1:
			return Node(nums[0])
		elif not nums:
			return None
		cen = (len(nums) - 1) // 2
		head = Node(nums[cen])
		head.left = self.convert(nums[:cen])
		head.right = self.convert(nums[cen + 1:])
		return head

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

	def sortedArrayToBST(self, nums):
		head = self.convert(nums)
		return self.pre(head)


class Solution:

	def inorder(self, nums, low, h, l):
		if low > h:
			return
		mid = (low + h) // 2
		l.append(nums[mid])
		self.inorder(nums, low, mid - 1, l)
		self.inorder(nums, mid + 1, h, l)

	def sortedArrayToBST(self, nums):
		(low, h) = (0, len(nums) - 1)
		l = []
		self.inorder(nums, low, h, l)
		return l


class Solution:

	def sortedArrayToBST(self, nums):
		lowest = 0
		highest = len(nums) - 1
		ans = []

		def BST(nums, lowest, highest, ans):
			if lowest > highest:
				return
			mid = (lowest + highest) // 2
			ans.append(nums[mid])
			BST(nums, lowest, mid - 1, ans)
			BST(nums, mid + 1, highest, ans)
		BST(nums, lowest, highest, ans)
		return ans


class Solution:

	def sortedArrayToBST(self, nums):
		n = (len(nums) - 1) // 2
		if n == 0:
			return nums
		item = [nums[n]]
		left = self.sortedArrayToBST(nums[:n])
		right = self.sortedArrayToBST(nums[n + 1:])
		return item + left + right


class Node:

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

class Solution:

	def sortedArrayToBST(self, nums):
		low = 0
		high = len(nums) - 1
		ans = []

		def ToBst(nums, ans, low, high):
			if low > high:
				return
			mid = (low + high) // 2
			ans.append(nums[mid])
			ToBst(nums, ans, low, mid - 1)
			ToBst(nums, ans, mid + 1, high)
		ToBst(nums, ans, low, high)
		return ans


class Node:

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

class Solution:

	def sortedArrayToBST(self, nums):
		res = []
		root = self.createTree(nums)
		res = self.preorder(root, res)
		return res

	def createTree(self, nums):
		if not nums:
			return None
		n = len(nums)
		if n % 2 == 0:
			mid = n // 2 - 1
		else:
			mid = n // 2
		root = Node(nums[mid])
		root.left = self.createTree(nums[:mid])
		root.right = self.createTree(nums[mid + 1:])
		return root

	def preorder(self, node, lst):
		if not node:
			return lst
		lst.append(node.data)
		self.preorder(node.left, lst)
		self.preorder(node.right, lst)
		return lst


class Node:

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

class Solution:

	def sortedArrayToBST(self, nums):

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

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


class Solution:

	def sortedArrayToBST(self, n):
		l = 0
		h = len(n) - 1
		a = []

		def tb(n, a, l, h):
			if l > h:
				return
			m = (l + h) // 2
			a.append(n[m])
			tb(n, a, l, m - 1)
			tb(n, a, m + 1, h)
		tb(n, a, l, h)
		return a


class Solution:

	def sortedArrayToBST(self, nums):
		l = 0
		e = len(nums) - 1
		ans = []
		self.anso(nums, l, e, ans)
		return ans

	def anso(self, nums, l, e, ans):
		if l > e:
			return
		else:
			mid = (l + e) // 2
			ans.append(nums[mid])
			self.anso(nums, l, mid - 1, ans)
			self.anso(nums, mid + 1, e, ans)


class Solution:

	def construct_bst_from_arr(self, arr, start, end, ans):
		if start > end:
			return None
		mid = (start + end) // 2
		ans.append(arr[mid])
		self.construct_bst_from_arr(arr, start, mid - 1, ans)
		self.construct_bst_from_arr(arr, mid + 1, end, ans)

	def sortedArrayToBST(self, nums):
		ans = []
		self.construct_bst_from_arr(nums, 0, len(nums) - 1, ans)
		return ans


class Node:

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

class Solution:

	def sortedArrayToBST(self, nums):
		root = self.d(nums, 0, len(nums) - 1)
		l = []
		self.dfs(root, l)
		return l

	def dfs(self, root, l):
		if root:
			l.append(root.data)
			self.dfs(root.left, l)
			self.dfs(root.right, l)

	def d(self, nums, i, j):
		if i > j:
			return None
		if i >= 0 and j < len(nums):
			m = int((i + j) / 2)
			root = Node(nums[m])
			root.left = self.d(nums, i, m - 1)
			root.right = self.d(nums, m + 1, j)
			return root
		return None


class Solution:

	def sortedArrayToBST(self, nums):
		s = 0
		e = len(nums) - 1
		root = self.makingtree(nums, s, e, [])
		return root

	def makingtree(self, nums, s, e, ans):
		if s > e:
			return
		mid = (s + e) // 2
		root = nums[mid]
		ans.append(root)
		self.makingtree(nums, s, mid - 1, ans)
		self.makingtree(nums, mid + 1, e, ans)
		return ans


class Solution:

	def BST(self, arr, left, right, node):
		if left > right:
			return
		mid = (left + right) // 2
		node.append(arr[mid])
		self.BST(arr, left, mid - 1, node)
		self.BST(arr, mid + 1, right, node)
		return node

	def sortedArrayToBST(self, nums):
		node = []
		return self.BST(nums, 0, len(nums) - 1, node)


class Node:

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

class Solution:

	def sortedArrayToBST(self, nums):
		ans = []

		def builder(i, j):
			if j < i:
				return
			mid = (i + j) // 2
			ans.append(nums[mid])
			builder(i, mid - 1)
			builder(mid + 1, j)
		builder(0, len(nums) - 1)
		return ans


class Solution:

	def sortedArrayToBST(self, nums):
		l = 0
		r = len(nums) - 1
		ans = []

		def helper(nums, ans, l, r):
			if l > r:
				return None
			m = (l + r) // 2
			ans.append(nums[m])
			helper(nums, ans, l, m - 1)
			helper(nums, ans, m + 1, r)
		helper(nums, ans, l, r)
		return ans


def util(nums, l, r):
	if l > r:
		return []
	mid = (l + r) // 2
	return [nums[mid]] + util(nums, l, mid - 1) + util(nums, mid + 1, r)

class Solution:

	def sortedArrayToBST(self, nums):
		return util(nums, 0, len(nums) - 1)


from math import floor

class Node:

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

class Solution:

	def sortedArrayToBST(self, nums):
		N = len(nums)
		center = floor((N - 1) / 2)
		root = Node(nums[center])

		def makeCenter(start, end, center, array, node):
			if center - start > 0:
				midLeft = floor((center + start - 1) / 2)
				node.left = Node(array[midLeft])
				makeCenter(start, center, midLeft, array, node.left)
			if end - (center + 1) > 0:
				midRight = floor((end + (center + 1) - 1) / 2)
				node.right = Node(array[midRight])
				makeCenter(center + 1, end, midRight, array, node.right)
			return
		makeCenter(0, N, center, nums, root)
		A = []

		def preOrder(node, A):
			A.append(node.data)
			if node.left:
				preOrder(node.left, A)
			if node.right:
				preOrder(node.right, A)
			return
		preOrder(root, A)
		return A


class TreeNode:

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

class Solution:

	def sortedArrayToBST(self, nums):

		def solve(nums):
			if not nums:
				return None
			if len(nums) % 2 != 0:
				mid = len(nums) // 2
			else:
				mid = len(nums) // 2 - 1
			root = TreeNode(nums[mid])
			root.left = solve(nums[:mid])
			root.right = solve(nums[mid + 1:])
			return root
		root = solve(nums)
		l = []

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


class Solution:

	def sortedArrayToBST(self, nums):
		a = []
		self.get(nums, a)
		return a

	def get(self, nums, a):
		n = len(nums)
		index = n // 2
		if n % 2 == 0:
			index = n // 2 - 1
		a.append(nums[index])
		if index > 0:
			self.get(nums[0:index], a)
		if index < n - 1:
			self.get(nums[index + 1:n], a)


class Solution:

	def sortedArrayToBST(self, nums):
		self.ans = []

		def bst(nums, a, b, temp):
			if a > b:
				return
			mid = (a + b) // 2
			temp.append(nums[mid])
			bst(nums, a, mid - 1, temp)
			bst(nums, mid + 1, b, temp)
			return temp
		return bst(nums, 0, len(nums) - 1, [])


class Solution:

	def sortedArrayToBST(self, nums):
		arr = []

		def helper(l, r, nums, arr):
			if l > r:
				return None
			mid = (l + r) // 2
			arr.append(nums[mid])
			helper(l, mid - 1, nums, arr)
			helper(mid + 1, r, nums, arr)
		helper(0, len(nums) - 1, nums, arr)
		return arr


class Solution:

	def sortedArrayToBST(self, arr):
		if len(arr) == 0:
			return []
		myList = []

		def help(arr):
			if len(arr) == 0:
				return
			elif len(arr) == 1:
				myList.append(arr[0])
			else:
				if len(arr) % 2 != 0:
					mid = len(arr) // 2
				else:
					mid = len(arr) // 2 - 1
				myList.append(arr[mid])
				if len(arr[:mid]) > 0:
					help(arr[:mid])
				if len(arr[mid + 1:]) > 0:
					help(arr[mid + 1:])
			return myList
		return help(arr)