Constructing a Binary Search Tree

Inspiration

MLH Challenge Day 2

What it does

It creates a binary search tree from a sorted array and prints a pre-order traversal of the BST

What I learned

A sorted array is better to construct a BST rather than building it from an unsorted array

"""
Construct BST
Send Feedback
Given a sorted integer array A of size n, which contains all unique elements. You need to construct a balanced BST from this input array. 
Return the root of constructed BST.
Note: If array size is even, take first mid as root.
Input format:
The first line of input contains an integer, which denotes the value of n. The following line contains n space separated integers, 
that denote the values of array.
Output Format:
The first and only line of output contains values of BST nodes, printed in pre order traversal.
"""
import queue
class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def constructBST(lst):
    if not lst:
        return None
    if len(lst) % 2 != 0:
        mid = (len(lst)) // 2
    else:
        mid = (len(lst)//2) - 1
    root = BinaryTreeNode(lst[mid])
    root.left = constructBST(lst[:mid])
    root.right = constructBST(lst[mid+1:])
    return root


def preOrder(root):
    # Given a binary tree, print the preorder traversal of the given tree. Pre-order
    # traversal is: Root LeftChild RightChild
    if root==None:
        return
    print(root.data, end=' ')
    preOrder(root.left)
    preOrder(root.right)

# Main
n=int(input())
if(n>0):
    lst=[int(i) for i in input().strip().split()]
else:
    lst=[]
root=constructBST(lst)
preOrder(root)

Built With

• python