Given an array of size N containing level order traversal of a BST. The task is to complete the function constructBst(), that construct the BST (Binary Search Tree) from its given level order traversal.
Example 1:
Input:
N = 9
BST[] = {7,4,12,3,6,8,1,5,10}
Output: 7 4 3 1 6 5 12 8 10
Explanation: After constructing BST, the
preorder traversal of BST is
7 4 3 1 6 5 12 8 10.
Example 2:
Input:
N = 6
BST[] = {1,3,4,6,7,8}
Output: 1 3 4 6 7 8
Explanation: After constructing BST, the
preorder traversal of BST is 1 3 4 6 7 8.
Your Task:
Your task is to complete the function constructBst() which has two arguments, first as the array containing level order traversal of BST and next argument as the length of array which return the root of the newly constructed BST. The preorder traversal of the tree is printed by the driver's code.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N).
Constraints:
1 <= N <= 10^{3}

Difficulty: MEDIUM
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N).

Starter code:
#User function Template for python3





#Function to construct the BST from its given level order traversal.

def constructBst(arr,n):

    #Your code here

    

Solutions:
def constructBst(arr, n):
	Q = []
	i = 1
	root = Node(arr[0])
	Q.append([root, float('-inf'), float('inf')])
	while i < n and len(Q) != 0:
		temp = Q.pop(0)
		if i < n and arr[i] < temp[0].data and (arr[i] > temp[1]):
			temp[0].left = Node(arr[i])
			Q.append([temp[0].left, temp[1], temp[0].data])
			i += 1
		if i < n and arr[i] > temp[0].data and (arr[i] < temp[2]):
			temp[0].right = Node(arr[i])
			Q.append([temp[0].right, temp[0].data, temp[2]])
			i += 1
	return root


from collections import deque

def constructBst(arr, n):
	if len(arr) == 0:
		return None
	root = Node(arr[0])
	q = deque()
	q.append((root, -2 ** 31, 2 ** 31))
	i = 1
	while len(q) > 0 and i < n:
		curr = q.popleft()
		mi = curr[1]
		ma = curr[2]
		if mi < arr[i] < curr[0].data:
			curr[0].left = Node(arr[i])
			q.append((curr[0].left, mi, curr[0].data))
			i += 1
		if i == n:
			break
		if curr[0].data < arr[i] < ma:
			curr[0].right = Node(arr[i])
			q.append((curr[0].right, curr[0].data, ma))
			i += 1
	return root


import math

def constructBst(arr, n):
	root = None
	for i in range(n):
		root = insert(root, arr[i])
	return root

def insert(root, x):
	if not root:
		return Node(x)
	if root.data < x:
		root.right = insert(root.right, x)
	elif root.data > x:
		root.left = insert(root.left, x)
	return root


import math

def constructBst(arr, n):
	if n == 0:
		return None
	nodes = [Node(arr[i]) for i in range(n)]
	root = nodes[0]
	q = []
	q.append([root, [-math.inf, root.data], [root.data, math.inf]])
	p = 1
	while q:
		e = q.pop(0)
		r = e[0]
		(ll, lh) = (e[1][0], e[1][1])
		(rl, rh) = (e[2][0], e[2][1])
		if p < n and ll < nodes[p].data < lh:
			r.left = nodes[p]
			p += 1
			q.append([r.left, [ll, r.left.data], [r.left.data, lh]])
		if p < n and rl < nodes[p].data < rh:
			r.right = nodes[p]
			p += 1
			q.append([r.right, [rl, r.right.data], [r.right.data, rh]])
	return root


def constructBst(arr, n):
	root = Node(arr[0])

	def insert(root, val):
		cur = root
		while cur:
			if cur.data >= val:
				if cur.left:
					cur = cur.left
				else:
					cur.left = Node(val)
					return
			elif cur.right:
				cur = cur.right
			else:
				cur.right = Node(val)
				return
	for i in range(1, n):
		insert(root, arr[i])
	return root


class Tree:

	def createnode(self, data):
		return Node(data)

	def insert(self, node, data):
		if node is None:
			return self.createnode(data)
		else:
			if data > node.data:
				node.right = self.insert(node.right, data)
			else:
				node.left = self.insert(node.left, data)
			return node

def constructBst(arr, n):
	bst = Tree()
	root = None
	root = bst.insert(root, arr[0])
	for i in range(1, n):
		root = bst.insert(root, arr[i])
	return root


class Solution:

	def check(self, a):
		if len(a) == 0:
			return None
		g = Node(a.pop(0))
		a1 = []
		a2 = []
		for i in a:
			if i < g.data:
				a1.append(i)
			else:
				a2.append(i)
		g.left = self.check(a1)
		g.right = self.check(a2)
		return g

def constructBst(arr, n):
	o = Solution()
	return o.check(arr)


def constructBst(arr, n):
	root = None
	root = insert(root, arr[0])
	for i in range(1, n):
		insert(root, arr[i])
	return root

def insert(root, key):
	if root is None:
		return Node(key)
	elif key < root.data:
		root.left = insert(root.left, key)
	else:
		root.right = insert(root.right, key)
	return root


from collections import deque

def constructBst(arr, n):
	root = Node(arr[0])
	q = deque([(root, float('-inf'), float('inf'))])
	i = 1
	while i < n:
		l = len(q)
		for _ in range(l):
			(cur, mn, mx) = q.popleft()
			if i < n and mn < arr[i] < cur.data:
				cur.left = Node(arr[i])
				q.append((cur.left, mn, cur.data))
				i += 1
			if i < n and cur.data < arr[i] < mx:
				cur.right = Node(arr[i])
				q.append((cur.right, cur.data, mx))
				i += 1
	return root


from collections import deque

def constructBst(arr, n):
	root = Node(arr[0])
	q = deque([(float('-inf'), root, float('inf'))])
	i = 1
	while i < n:
		(low, node, high) = q.popleft()
		if low < arr[i] < node.data:
			left_node = Node(arr[i])
			node.left = left_node
			q.append((low, left_node, node.data))
			i += 1
		if i < n and node.data < arr[i] < high:
			right_node = Node(arr[i])
			node.right = right_node
			q.append((node.data, right_node, high))
			i += 1
	return root


import collections

def constructBst(arr, n):
	if n == 0:
		return None
	root = Node(arr[0])
	for i in range(1, n):
		insert(root, arr, n, i)
	return root

def insert(root, a, n, i):
	if root.data > a[i]:
		if root.left:
			insert(root.left, a, n, i)
		else:
			root.left = Node(a[i])
	if root.data < a[i]:
		if root.right:
			insert(root.right, a, n, i)
		else:
			root.right = Node(a[i])


import collections

def constructBst(arr, n):
	if n == 0:
		return None
	root = Node(arr[0])
	i = 1
	x = collections.deque()
	x.append([root, float('-inf'), float('inf')])
	while i < n:
		(node, mini, maxi) = x.popleft()
		if i < n and arr[i] < node.data and (arr[i] > mini):
			node.left = Node(arr[i])
			i += 1
			x.append([node.left, mini, node.data])
		if i < n and arr[i] > node.data and (arr[i] < maxi):
			node.right = Node(arr[i])
			i += 1
			x.append([node.right, node.data, maxi])
	return root


from collections import deque
import math

def constructBst(arr, n):
	que = deque()
	head = Node(arr[0])
	que.append([head, -math.inf, math.inf])
	i = 1
	while i < len(arr):
		ele = arr[i]
		(frontNode, low, high) = que[0]
		if not frontNode.left and low <= ele < frontNode.data:
			node = Node(ele)
			frontNode.left = node
			que.append([node, low, frontNode.data - 1])
			i += 1
		elif not frontNode.right and frontNode.data < ele <= high:
			node = Node(ele)
			frontNode.right = node
			que.append([node, frontNode.data + 1, high])
			i += 1
		else:
			que.popleft()
	return head


def insert(head, data):
	if not head:
		return Node(data)
	elif data <= head.data:
		head.left = insert(head.left, data)
	else:
		head.right = insert(head.right, data)
	return head

def constructBst(arr, n):
	if not arr:
		return None
	root = None
	for i in range(n):
		root = insert(root, arr[i])
	return root


def constructBst(arr, n):
	queue = []
	root = Node(None)
	queue.append([root, float('-inf'), float('inf'), 'L'])
	i = 0
	while len(queue) != 0 and i < n:
		parent = queue[0][0]
		start = queue[0][1]
		end = queue[0][2]
		check = queue[0][3]
		queue.pop(0)
		if start < arr[i] and end > arr[i]:
			node = Node(arr[i])
			if check == 'L':
				parent.left = node
			else:
				parent.right = node
			queue.append([node, start, arr[i], 'L'])
			queue.append([node, arr[i], end, 'R'])
			i += 1
	root = root.left
	return root


def formbst(root, node):
	if root == None:
		root = Node(node)
		return root
	if node < root.data:
		root.left = formbst(root.left, node)
	else:
		root.right = formbst(root.right, node)
	return root

def constructBst(arr, n):
	root = None
	for i in arr:
		root = formbst(root, i)
	return root


from collections import deque

def constructBst(arr, n):
	root = Node(arr[0])

	def insert(root, k):
		if not root:
			return Node(k)
		elif k <= root.data:
			root.left = insert(root.left, k)
		else:
			root.right = insert(root.right, k)
		return root
	for i in range(1, n):
		insert(root, arr[i])
	return root


from collections import deque
INV = 10 ** 9

def constructBst(A, N):
	root = Node(A[0])
	q1 = deque([(-INV, A[0], root), (A[0], INV, root)])
	i = 1
	while i < N:
		v = A[i]
		while q1:
			(L, R, par) = q1.popleft()
			if L < v < R:
				nd = Node(v)
				if v < par.data:
					par.left = nd
				else:
					par.right = nd
				q1.append((L, v, nd))
				q1.append((v, R, nd))
				i += 1
				break
	return root


from collections import deque

def constructBst(A, N):
	root = Node(A[0])
	for i in range(1, N):
		v = A[i]
		(prev, nd) = (None, root)
		while nd:
			prev = nd
			if v < nd.data:
				nd = nd.left
			else:
				nd = nd.right
		if v < prev.data:
			prev.left = Node(v)
		else:
			prev.right = Node(v)
	return root


def constructBst(arr, n):
	root = Node(arr[0])
	lo = float('-inf')
	hi = float('inf')
	q = [(root, lo, hi)]
	i = 1
	while q and i < len(arr):
		(node, l, h) = q.pop(0)
		if arr[i] < node.data and arr[i] > l:
			node.left = Node(arr[i])
			q.append((node.left, l, node.data))
			i += 1
		if i < len(arr) and arr[i] > node.data and (arr[i] < h):
			node.right = Node(arr[i])
			q.append((node.right, node.data, h))
			i += 1
	return root


def constructBst(arr, n):
	root = None
	for i in arr:
		root = insertBST(root, i)
	return root

def insertBST(root, item):
	if root is None:
		return Node(item)
	if root.data > item:
		root.left = insertBST(root.left, item)
	if root.data < item:
		root.right = insertBST(root.right, item)
	return root


def constructBst(arr, n):
	root = None
	if n == 0:
		return root
	while len(arr) > 0:
		node = Node(arr.pop(0))
		if root is None:
			root = node
		else:
			found = False
			parentnode = root
			while not found:
				if node.data <= parentnode.data:
					if parentnode.left is None:
						parentnode.left = node
						found = True
					else:
						parentnode = parentnode.left
				elif parentnode.right is None:
					parentnode.right = node
					found = True
				else:
					parentnode = parentnode.right
	return root


def insert(root, val):
	if not root:
		return Node(val)
	if root.data > val:
		root.left = insert(root.left, val)
	elif root.data < val:
		root.right = insert(root.right, val)
	return root

def constructBst(arr, n):
	r = None
	for i in arr:
		r = insert(r, i)
	return r


def getnode(data):
	newnode = Node(data)
	newnode.data = data
	newnode.left = None
	newnode.right = None
	return newnode

def lot(root, data):
	if root == None:
		root = getnode(data)
		return root
	if data <= root.data:
		root.left = lot(root.left, data)
	else:
		root.right = lot(root.right, data)
	return root

def constructBst(arr, n):
	if n == 0:
		return None
	root = None
	for i in range(0, n):
		root = lot(root, arr[i])
	return root


def LevelOrder(root, data):
	if root == None:
		root = Node(data)
		return root
	if data <= root.data:
		root.left = LevelOrder(root.left, data)
	else:
		root.right = LevelOrder(root.right, data)
	return root

def constructBst(arr, n):
	if n == 0:
		return None
	root = None
	for i in range(0, n):
		root = LevelOrder(root, arr[i])
	return root


def utility(arr, index, n, low, high):
	root = Node(arr[index])
	index += 1
	q = [[root, low, high]]
	while index < n:
		[ret, low, high] = q.pop(0)
		left = arr[index]
		if left > low and left < ret.data:
			leftOne = Node(left)
			ret.left = leftOne
			q.append([leftOne, low, ret.data])
			index += 1
		if index >= len(arr):
			break
		right = arr[index]
		if right > ret.data and right < high:
			rightOne = Node(right)
			ret.right = rightOne
			q.append([rightOne, ret.data, high])
			index += 1
	return root

def constructBst(arr, n):
	index = 0
	low = -100000.0
	high = 100000.0
	root = Node(arr[index])
	index += 1
	q = [[root, low, high]]
	while index < n:
		[ret, low, high] = q.pop(0)
		left = arr[index]
		if left > low and left < ret.data:
			leftOne = Node(left)
			ret.left = leftOne
			q.append([leftOne, low, ret.data])
			index += 1
		if index >= len(arr):
			break
		right = arr[index]
		if right > ret.data and right < high:
			rightOne = Node(right)
			ret.right = rightOne
			q.append([rightOne, ret.data, high])
			index += 1
	return root


def insert_node(root, value):
	if root is None:
		return Node(value)
	if root.data < value:
		root.right = insert_node(root.right, value)
	else:
		root.left = insert_node(root.left, value)
	return root

def constructBst(arr, n):
	root = Node(arr[0])
	for x in arr[1:]:
		root = insert_node(root, x)
	return root


def insert(root, value):
	if root is None:
		root = Node(value)
		return root
	if value > root.data:
		root.right = insert(root.right, value)
	else:
		root.left = insert(root.left, value)
	return root

def constructBst(arr, n):
	root = None
	for i in arr:
		root = insert(root, i)
	return root


class bst:

	def __init__(self):
		self.start = None

	def insert(self, node):
		if self.start == None:
			self.start = node
		else:
			tmp = self.start
			while tmp != None:
				if tmp.data > node.data:
					if tmp.left == None:
						tmp.left = node
						break
					tmp = tmp.left
				elif tmp.data < node.data:
					if tmp.right == None:
						tmp.right = node
						break
					tmp = tmp.right

def constructBst(arr, n):
	b = bst()
	for i in arr:
		b.insert(Node(i))
	return b.start

class Node:

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

def preOrder(root):
	if root is None:
		return
	print(root.data, end=' ')
	preOrder(root.left)
	preOrder(root.right)

def main():
	testcases = int(input())
	while testcases > 0:
		root = None
		sizeOfArray = int(input())
		arr = [int(x) for x in input().strip().split()]
		root = constructBst(arr, sizeOfArray)
		preOrder(root)
		print()
		testcases -= 1
if __name__ == '__main__':
	main()


def LevelOrder(root, data):
	if root == None:
		root = Node(data)
		return root
	if data <= root.data:
		root.left = LevelOrder(root.left, data)
	else:
		root.right = LevelOrder(root.right, data)
	return root

def constructBst(arr, n):
	if n == 0:
		return None
	root = None
	for i in range(n):
		root = LevelOrder(root, arr[i])
	return root

class Node:

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

def preOrder(root):
	if root is None:
		return
	print(root.data, end=' ')
	preOrder(root.left)
	preOrder(root.right)

def main():
	testcases = int(input())
	while testcases > 0:
		root = None
		sizeOfArray = int(input())
		arr = [int(x) for x in input().strip().split()]
		root = constructBst(arr, sizeOfArray)
		preOrder(root)
		print()
		testcases -= 1
if __name__ == '__main__':
	main()


class Node:

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

def getNode(data):
	newNode = Node(data)
	newNode.data = data
	newNode.left = None
	newNode.right = None
	return newNode

def LevelOrder(root, data):
	if root == None:
		root = getNode(data)
		return root
	if data <= root.data:
		root.left = LevelOrder(root.left, data)
	else:
		root.right = LevelOrder(root.right, data)
	return root

def constructBst(arr, n):
	if n == 0:
		return None
	root = None
	for i in range(0, n):
		root = LevelOrder(root, arr[i])
	return root


def construct(root, X):
	if not root:
		root = Node(X)
		return root
	if root.data > X:
		root.left = construct(root.left, X)
	else:
		root.right = construct(root.right, X)
	return root

def constructBst(arr, n):
	if n == 0:
		return None
	root = None
	for i in range(n):
		root = construct(root, arr[i])
	return root


def insert(root, k):
	if root == None:
		temp = Node(k)
		return temp
	if root.data > k:
		root.left = insert(root.left, k)
	elif root.data < k:
		root.right = insert(root.right, k)
	return root

def constructBst(arr, n):
	root = Node(arr[0])
	for i in range(1, n):
		insert(root, arr[i])
	return root


def constructBst(arr, n):
	if len(arr) == 0:
		return None
	elif len(arr) == 1:
		return Node(arr[0])
	else:
		rv = arr[0]
		root = Node(rv)
		lst = [i for i in arr if i < rv]
		rst = [i for i in arr if i > rv]
		root.left = constructBst(lst, n)
		root.right = constructBst(rst, n)
		return root


def constructBst(arr, n):

	def insert(root, data):
		if data < root.data:
			if root.left:
				insert(root.left, data)
			else:
				root.left = Node(data)
		elif root.right:
			insert(root.right, data)
		else:
			root.right = Node(data)
	root = arr.pop(0)
	root = Node(root)
	for i in arr:
		insert(root, i)
	return root


def constructBst(arr, n):
	if n == 0:
		return None
	root = Node(arr[0])
	lesserElements = []
	greaterorEqualElements = []
	for i in range(1, n):
		if arr[i] < root.data:
			lesserElements.append(arr[i])
		else:
			greaterorEqualElements.append(arr[i])
	root.left = constructBst(lesserElements, len(lesserElements))
	root.right = constructBst(greaterorEqualElements, len(greaterorEqualElements))
	return root


from collections import deque

class NodeRange:

	def __init__(self, node, min_val, max_val):
		self.node = node
		self.min = min_val
		self.max = max_val

def constructBst(levelorder, n):
	root_node = Node(levelorder[0])
	root_nr = NodeRange(root_node, float('-inf'), float('inf'))
	que = deque([root_nr])
	i = 1
	while que:
		curr = que.popleft()
		parent = curr.node
		(min_val, max_val) = (curr.min, curr.max)
		if i < n and levelorder[i] < parent.data and (levelorder[i] > min_val):
			parent.left = Node(levelorder[i])
			que.append(NodeRange(parent.left, min_val, parent.data))
			i += 1
		if i < n and levelorder[i] > parent.data and (levelorder[i] < max_val):
			parent.right = Node(levelorder[i])
			que.append(NodeRange(parent.right, parent.data, max_val))
			i += 1
	return root_node


import sys
from collections import deque

def constructBst(arr, s):
	q = deque()
	root = Node(arr[0])
	q.append((root, -sys.maxsize, sys.maxsize))
	i = 1
	while i < s:
		(n, l, r) = q[0]
		q.popleft()
		if l < arr[i] < n.data:
			temp = Node(arr[i])
			n.left = temp
			q.append((temp, l, n.data))
			i += 1
		if i < s and r > arr[i] > n.data:
			temp = Node(arr[i])
			n.right = temp
			q.append((temp, n.data, r))
			i += 1
	return root


def constructBst(arr, n):
	if len(arr) <= 0:
		return
	root = Node(arr[0])
	r = []
	l = []
	for i in arr[1:]:
		if i > root.data:
			r.append(i)
		else:
			l.append(i)
	root.left = constructBst(l, n)
	root.right = constructBst(r, n)
	return root


from collections import deque

def constructBst(arr, n=0):
	if len(arr) == 0:
		return None
	leftTree = []
	rightTree = []
	root = Node(arr[0])
	for i in range(1, len(arr)):
		if arr[i] > arr[0]:
			rightTree.append(arr[i])
		else:
			leftTree.append(arr[i])
	root.left = constructBst(leftTree)
	root.right = constructBst(rightTree)
	return root


def solve(root, x):
	if root == None:
		return Node(x)
	if root.data > x:
		root.left = solve(root.left, x)
	if root.data < x:
		root.right = solve(root.right, x)
	return root

def constructBst(arr, n):
	root = None
	for i in range(n):
		root = solve(root, arr[i])
	return root


from collections import deque

class Node:

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

def constructBst(a, n):
	if n == 0:
		return root
	root = Node(a[0])
	q = deque([])
	q.append([root, -99999, 99999])
	i = 1
	while len(q) > 0 and i < n:
		(temp, s, e) = q.popleft()
		if i < n and a[i] > s and (a[i] < temp.data):
			temp.left = Node(a[i])
			q.append([temp.left, s, temp.data])
			i += 1
		else:
			temp.left = None
		if i < n and a[i] > temp.data and (a[i] < e):
			temp.right = Node(a[i])
			q.append([temp.right, temp.data, e])
			i += 1
		else:
			temp.right = None
	return root


def make_tree(root, ele):
	if root == None:
		return Node(ele)
	if root.data < ele:
		root.right = make_tree(root.right, ele)
	else:
		root.left = make_tree(root.left, ele)
	return root

def constructBst(arr, n):
	root = None
	for i in range(n):
		root = make_tree(root, arr[i])
	return root


import math
from collections import deque

def constructBst(arr, n):
	q = deque()
	root = Node(arr[0])
	idx = 1
	q.append((root, -math.inf, math.inf))
	while q:
		(node, curr_min, curr_max) = q.popleft()
		if idx < n and arr[idx] < node.data and (arr[idx] > curr_min):
			l = Node(arr[idx])
			idx += 1
			node.left = l
			q.append((l, curr_min, node.data))
		if idx < n and arr[idx] > node.data and (arr[idx] < curr_max):
			r = Node(arr[idx])
			idx += 1
			node.right = r
			q.append((r, node.data, curr_max))
	return root


def levelOrder(root, val):
	if root == None:
		root = Node(val)
		return root
	if root.data > val:
		root.left = levelOrder(root.left, val)
	else:
		root.right = levelOrder(root.right, val)
	return root

def constructBst(arr, n):
	if arr == []:
		return
	root = None
	for i in range(len(arr)):
		root = levelOrder(root, arr[i])
	return root


import math

def constructBst(arr, n):
	root = None
	if n == 0:
		return root
	root = Node(arr[0])
	q = [(root, -1 * math.inf, math.inf)]
	i = 1
	while len(q) and i < n:
		(parent, lmin, rmax) = q.pop(0)
		if parent.data > arr[i] and arr[i] > lmin:
			node = Node(arr[i])
			i += 1
			parent.left = node
			q.append((node, lmin, parent.data))
		if i < n and parent.data < arr[i] and (rmax > arr[i]):
			node = Node(arr[i])
			i += 1
			parent.right = node
			q.append((node, parent.data, rmax))
	return root


def insert(root, x):
	parent = None
	while root is not None:
		parent = root
		if x < root.data:
			root = root.left
		else:
			root = root.right
	if x < parent.data:
		parent.left = Node(x)
	else:
		parent.right = Node(x)

def constructBst(arr, n):
	root = Node(arr[0])
	for x in arr[1:]:
		insert(root, x)
	return root


def constructBst(arr, n):
	i = 1
	if len(arr) == 0:
		return None
	else:
		root = Node(arr[0])
		while i < len(arr):
			t = Node(arr[i])
			i += 1
			insertNode(root, t)
	return root

def insertNode(root, t):
	if root == None:
		root = t
		return root
	if t.data < root.data:
		root.left = insertNode(root.left, t)
	elif t.data > root.data:
		root.right = insertNode(root.right, t)
	return root


class Node:

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

def constructBst(arr, n):
	if len(arr) == 0:
		return
	else:
		node = Node(arr[0])
		leftlevelorder = []
		rightlevelorder = []
		for i in range(1, len(arr)):
			if arr[i] > arr[0]:
				rightlevelorder.append(arr[i])
			else:
				leftlevelorder.append(arr[i])
		node.left = constructBst(leftlevelorder, n)
		node.right = constructBst(rightlevelorder, n)
		return node


def constructBst(arr, n):
	if n == 0:
		return None
	root = Node(arr[0])
	q = [[root, float('-inf'), float('inf')]]
	i = 1
	while len(q) and i < n:
		(temp, s, e) = q.pop(0)
		if arr[i] > s and temp.data > arr[i]:
			temp.left = Node(arr[i])
			i += 1
			q.append([temp.left, s, temp.data])
		else:
			temp.left = None
		if i < n:
			if temp.data < arr[i] and e > arr[i]:
				temp.right = Node(arr[i])
				i += 1
				q.append([temp.right, temp.data, e])
			else:
				temp.right = None
	return root


def constructBst(arr, n):
	root = None
	for i in arr:
		root = insert(root, i)
	return root

def insert(root, Key):
	if root is None:
		temp = Node(Key)
		return temp
	if root.data < Key:
		root.right = insert(root.right, Key)
	if root.data > Key:
		root.left = insert(root.left, Key)
	return root


def constructBst(arr, n):
	if len(arr) == 0:
		return None
	root = Node(arr[0])
	for val in arr[1:]:
		constructBSTUtill(root, val)
	return root

def constructBSTUtill(root, val):
	if root is None:
		return Node(val)
	if root.data < val:
		root.right = constructBSTUtill(root.right, val)
	elif root.data > val:
		root.left = constructBSTUtill(root.left, val)
	return root


def constructBst(arr, n):
	if n is 0:
		return None
	root = None
	for i in range(n):
		root = helper(root, arr[i])
	return root

def helper(root, x):
	if root is None:
		node = Node(x)
		return node
	if root.data < x:
		root.right = helper(root.right, x)
	else:
		root.left = helper(root.left, x)
	return root


def Level(root, value):
	if root == None:
		return Node(value)
	elif root.data > value:
		root.left = Level(root.left, value)
	elif root.data < value:
		root.right = Level(root.right, value)
	return root

def constructBst(arr, n):
	if n == 0:
		return None
	root = None
	for i in range(0, n):
		root = Level(root, arr[i])
	return root


def constructBst(arr, n):
	ino = sorted(arr)
	idx = 0

	def build(root, data):
		if not root:
			root = Node(data)
			return root
		if data < root.data:
			root.left = build(root.left, data)
		else:
			root.right = build(root.right, data)
		return root
	root = None
	for i in range(n):
		root = build(root, arr[i])
	return root


def constructBst(arr, n):
	if n == 0:
		return
	root = Node(arr[0])
	head = root
	queue = [(root, -float('inf'), root.data), (root, root.data, float('inf'))]
	i = 1
	while queue and i < n:
		(root, start, end) = queue.pop(0)
		if start < arr[i] and arr[i] < end:
			node = Node(arr[i])
			if arr[i] < root.data:
				root.left = node
				queue.append((node, start, node.data))
				queue.append((node, node.data, root.data))
			else:
				root.right = node
				queue.append((node, root.data, node.data))
				queue.append((node, node.data, end))
			i += 1
	return head


def levelOrder(root, xMin, xMax, arr, i, n):
	last_check = False
	for j in range(i, n):
		v = arr[j]
		if v <= xMin or v >= xMax:
			continue
		if v < root.data:
			if root.left:
				continue
			root.left = Node(v)
			levelOrder(root.left, xMin, root.data, arr, j + 1, n)
		elif v > root.data:
			root.right = Node(v)
			levelOrder(root.right, root.data, xMax, arr, j + 1, n)
			return root
		else:
			raise Exception('duplicate value {}'.format(v))
	return root

def constructBst(arr, n):
	root = Node(arr[0])
	return levelOrder(root, 0, float('inf'), arr, 1, n)


def constructBst(arr, n):
	new = Node(arr[0])
	for i in range(1, n):
		new1 = Node(arr[i])
		n = new
		while n is not None:
			if new1.data < n.data:
				if n.left:
					n = n.left
				else:
					n.left = new1
					break
			elif new1.data > n.data:
				if n.right:
					n = n.right
				else:
					n.right = new1
					break
	return new


def constructBst(arr, n):
	root = None
	for ele in arr:
		if root is None:
			root = Node(ele)
			continue
		current = root
		while current:
			prev = current
			if ele < current.data:
				current = current.left
				if current is None:
					prev.left = Node(ele)
			elif ele > current.data:
				current = current.right
				if current is None:
					prev.right = Node(ele)
	return root


from collections import deque

class NodeDetails:

	def __init__(self, node, lr, rr):
		self.node = node
		self.lr = lr
		self.rr = rr

def constructBst(arr, n):
	q = deque()
	root = None
	q.append(NodeDetails(None, -1000000000.0, 1000000000.0))
	idx = 0
	while q and idx < n:
		temp = q.popleft()
		curNode = Node(arr[idx])
		if arr[idx] < temp.lr or arr[idx] > temp.rr:
			continue
		elif temp.node == None:
			root = curNode
		elif curNode.data <= temp.node.data:
			temp.node.left = curNode
		else:
			temp.node.right = curNode
		idx += 1
		q.append(NodeDetails(curNode, temp.lr, curNode.data))
		q.append(NodeDetails(curNode, curNode.data, temp.rr))
	return root


from collections import deque

class Info:

	def __init__(self, obj, lb, rb):
		self.par = obj
		self.lb = lb
		self.rb = rb

def constructBst1(arr, n):
	idx = 0
	q = deque()
	q.append(Info(None, -1000000000.0, 1000000000.0))
	root = None
	while q and idx < n:
		temp = q.popleft()
		if arr[idx] < temp.lb or arr[idx] > temp.rb:
			continue
		currNode = Node(arr[idx])
		idx += 1
		if temp.par == None:
			root = currNode
		elif temp.par.data >= arr[idx - 1]:
			temp.par.left = currNode
		else:
			temp.par.right = currNode
		q.append(Info(currNode, temp.lb, currNode.data))
		q.append(Info(currNode, currNode.data, temp.rb))
	return root

def constructBst(arr, n):
	root = None
	root = None
	for i in range(n):
		root = buildTree(root, arr[i])
	return root

def buildTree(root, val):
	if root == None:
		return Node(val)
	else:
		if root.data >= val:
			root.left = buildTree(root.left, val)
		else:
			root.right = buildTree(root.right, val)
		return root


from collections import deque

class Info:

	def __init__(self, obj, lb, rb):
		self.par = obj
		self.lb = lb
		self.rb = rb

def constructBst(arr, n):
	idx = 0
	q = deque()
	q.append(Info(None, -1000000000.0, 1000000000.0))
	root = None
	while q and idx < n:
		temp = q.popleft()
		if arr[idx] < temp.lb or arr[idx] > temp.rb:
			continue
		currNode = Node(arr[idx])
		idx += 1
		if temp.par == None:
			root = currNode
		elif temp.par.data >= arr[idx - 1]:
			temp.par.left = currNode
		else:
			temp.par.right = currNode
		q.append(Info(currNode, temp.lb, currNode.data))
		q.append(Info(currNode, currNode.data, temp.rb))
	return root