Convert Level Order Traversal to BST Python

PROGRAM TO CONSTRUCT BST FROM ITS GIVEN LEVEL ORDER TRAVERSAL




import math

  

# node of a BST

class Node: 

    def __init__(self,data): 

        self.data = data 

        self.left = None

        self.right = None

  

# function to get a new node

def getNode( data):

      

    # Allocate memory

    newNode = Node(data)

      

    # put in the data 

    newNode.data = data

    newNode.left =None

    newNode.right = None

    return newNode

  

# function to construct a BST from

# its level order traversal

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

  

# function to print the inorder traversal

def inorderTraversal( root):

    if (root == None):

        return None

      

    inorderTraversal(root.left)

    print(root.data,end = " ")

    inorderTraversal(root.right) 

  

# Driver program

if __name__=='__main__': 

  

    arr = [7, 4, 12, 3, 6, 8, 1, 5, 10]

    n = len(arr)

      

    root = constructBst(arr, n)

      

    print("Inorder Traversal: ", end = "")

    root = inorderTraversal(root)




OUTPUT:

Inorder Traversal: 1 3 4 5 6 7 8 10 12

CREDITS: https://www.geeksforgeeks.org/construct-bst-given-level-order-traversal/