Program to construct BST from level order traversal

Description: in-order=[13,14,15,20,23,22,28] level=[20,14,23,13,15,22,28] In level order array first element is root of the tree.20 is the root element. now search this root element in the given in-order array when root element is find in this in-order
array.now create newroot take this as a root and return new root recursively. store inorder index
point as a new index position to paas in left subtree and right subtree for calling recursive Bstree().
20 left subtree / \ right subtree [13,14,15] [23,22,28] 20 left subtree / \ right subtree 14 22 / \ / \ 13 15 23 28
Code:
class Node: def __init__(self, data): self.left = None self.right = None self.node = data def Bstree(level,inorder): # check if inorder have element or not. if inorder: for i in range(0,len(level)): # check if level element is equal to in-order element.if both element is # equal then create new node and store the same value in it. if level[i] in inorder: new_root=Node(level[i]) #store index value of level elementin new variable which is same in inorder element. this new index value is passed inside recursive function. io_new=inorder.index(level[i]) break if not inorder: return new_root #index passes in left subtree in range start to io_new-1 new_root.left=Bstree(level,inorder[0:io_new]) #index passes in right subtree in range io_new to length of inorder. new_root.right=Bstree(level,inorder[io_new+1:len(inorder)]) return new_root def traverse_inorder(root): if root==None: return traverse_inorder(root.left) print(root.node,end=' ') traverse_inorder(root.right) level=[20,14,23,13,15,22,28] inorder=[13,14,15,20,23,22,28] a=len(inorder) root=Bstree(level,inorder) traverse_inorder(root) Output: 13 14 15 20 23 22 28

More Articles of Akrati Sharma:

Name Views Likes
Python numpy program to generate random number 834 0
Program to construct BST from level order traversal 643 2
Python numpy program to find sum the diagonal elements of the matrix 8457 1
Python find sum the diagonal elements of the matrix 1605 0
python numpy find the transpose of a matrix 393 0
Python numpy convert a csv file date to a matrix 492 1
Python program to read configuration file 382 1
Python program to convert doc file into pdf file. 997 19
Python program to add new page at the end of a pdf file 310 18
Python Program to find sink odd nodes in binary tree. 436 14
creating project in pythons scrapy library 405 16
Python program to check given array of size n can represent binary search tree of n levels or not. 298 16
Python program to find out greater sum tree elements of binary search tree 306 17
Selectors of scrapy library 396 24
Introduction to python scrapy library 314 16
Python Program to find an element in tuple by value using in and not in 288 18
Find an element in tuple by value using in and not in : 93 25
Python program to count Half Nodes in Binary Tree recursion 443 20
Python Program to find top three elements in binary tree. 262 20
Python program to count half nodes in binary tree without recursion 374 14
Python program to find deepest right leaf node in a binary tree using recursion. 350 18
Python program to convert a given tree to its Sumtree 489 26
Python program to convert a tree into its sum tree 84 21
Python Program to Convert Binary tree into Binary Search Tree 381 17
Python Program to check if each internal node of a BST has exactly one child 334 18
Python Program to find median of binary search tree 637 11
Python Program to find an Element into a Binary tree. 261 18
Python program to replace every element with the least greater element on its right 326 18
Python Program to delete an element at specific index in tuple. 20 13
Python program to insert an element to specific position in tuple 361 20
Python program to insert an element at specific position in tuple. 13 11
Python Program to append an element in tuple at the end. 313 20
Python Program to count subtree that sum up to a given value x 558 20
Python program to print all root to leaf paths with there relative positions 312 16
Python program to check given tree is Sumtree or not 412 16
Python program to find sum of nodes at maximum depth of a binary tree 505 21
Python Program to replace an element at specific index in tuple. 354 24
Python program to find given key x in binary tree 289 14
Python program to find vertical width of binary tree 352 15
Python program to find mirror of a given node in binary tree 369 19
Python program to find largest subtree sum in a tree 260 18
Python Program to calculate the size of tree without recursion 328 19
Python Program to find tilt of binary tree 452 18
Python Program to find maximum node in left subtree in binay tree. 240 16
Python program to convert a List to Dictionary with same Value. 278 19
Python program to count minimum swap require to construct Binary Search Tree from Binary tree 461 18
Program to construct BST from level order traversal 354 24
Python Program to delete an element at specific index in tuple. 572 21
Python Program to print all the elements in Binary Search tree. 1324 14