The following Python program creates a balanced Binary Tree from a given sorted list Θ(length of sorted list)
class SortedBST:
class Node:
def __init__(self, val):
self.value = val
self.left = None
self.right = None
def __init__(self, nos):
self.nos = nos
self.root = None
self.root = self.initBST(self.root, 0, len(nos) - 1)
def initBST(self, node, low, high):
mid = (low + high) >> 1
node = self.Node(self.nos[mid])
if low < mid:
node.left = self.initBST(node.left, low, mid-1)
if high > mid:
node.right = self.initBST(node.right, mid+1, high)
return node
def BFS(self):
from collections import deque
q = deque()
q.append(self.root)
while(q):
qv = q.popleft()
print(qv.value)
if qv.left != None:
q.append(qv.left)
if qv.right != None:
q.append(qv.right)
sortedList = sorted(list(map(int, input().split())))
sortedBst = SortedBST(sortedList)
sortedBst.BFS()
