Construct BST from its given level order traversal | Python implementation to construct a BST from its level order traversal ; node of a BST ; function to get a new node ; Allocate memory ; put in the data ; function to construct a BST from its level order traversal ; function to print the inorder traversal ; Driver program
import math NEW_LINE class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def getNode ( data ) : NEW_LINE INDENT newNode = Node ( data ) NEW_LINE newNode . data = data NEW_LINE newNode . left = None NEW_LINE newNode . right = None NEW_LINE return newNode NEW_LINE DEDENT def LevelOrder ( root , data ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT root = getNode ( data ) NEW_LINE return root NEW_LINE DEDENT if ( data <= root . data ) : NEW_LINE INDENT root . left = LevelOrder ( root . left , data ) NEW_LINE DEDENT else : NEW_LINE INDENT root . right = LevelOrder ( root . right , data ) NEW_LINE DEDENT return root NEW_LINE DEDENT def constructBst ( arr , n ) : NEW_LINE INDENT if ( n == 0 ) : NEW_LINE INDENT return None NEW_LINE DEDENT root = None NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT root = LevelOrder ( root , arr [ i ] ) NEW_LINE DEDENT return root NEW_LINE DEDENT def inorderTraversal ( root ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return None NEW_LINE DEDENT inorderTraversal ( root . left ) NEW_LINE print ( root . data , end = " ▁ " ) NEW_LINE inorderTraversal ( root . right ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 7 , 4 , 12 , 3 , 6 , 8 , 1 , 5 , 10 ] NEW_LINE n = len ( arr ) NEW_LINE root = constructBst ( arr , n ) NEW_LINE print ( " Inorder ▁ Traversal : ▁ " , end = " " ) NEW_LINE root = inorderTraversal ( root ) NEW_LINE DEDENT