Level order tree traversal in Python
A tree data structure can be traversed in many ways. Generally, there are two types of tree traversal(Breadth-first search and Depth-first search). In this tutorial, we will learn about level order traversal( Breadth-first search ) in Python.
Python: Level order tree traversal
We will create a binary tree and traverse the tree in level order. Level 0 is the root node( 5 ), then we traverse to the next level and traverse each node present at that level( 2, 7 ). In the same way, all the nodes in the tree are visited in level order.
class Tree: def __init__(node,value): node.value = value node.right = None node.left = None def create_node(node,value): if (node.value is None): node.value = value else: if( value < node.value ): if (node.left is None): node.left = Tree(value) else: node.left.create_node(value) elif( value > node.value ): if ( node.right is None): node.right = Tree(value) else: node.right.create_node(value) Root = Tree(5) Root.create_node(7) Root.create_node(2) Root.create_node(3) Root.create_node(6) Root.create_node(1) Root.create_node(8)
As the name of the algorithm suggests, it explores the tree level by level. Therefore the above binary tree can be traversed in the order 5 2 7 1 3 6 8.
def find_height(node,Root): if (Root is None): return 0 else: l_subtree = node.find_height(Root.left) r_subtree= node.find_height(Root.right) return max(l_subtree,r_subtree)+1 def level_order(node,Root): height = node.find_height(Root) for i in range(0,height ): node.traversal(Root,i) def traversal(node,Root,level): if Root==None: return elif level==0: print(Root.value,end = ' ') elif level >0: node.traversal(Root.left,level-1) node.traversal(Root.right,level-1)
Explanation:
- First, we have to find the height of the tree using a recursive function. So that we can iterate through the number of levels.
- After finding the height, we will traverse each level using the function ‘level_order’ and traverse each node present in that level using the recursive function ‘traversal’.
- This function will print 2 and 7 when the level is one and 1, 3, 6, 8 when the level is two.
Here is how the complete code should look like
class Tree: def __init__(node,value): node.value = value node.right = None node.left = None def create_node(node,value): if (node.value is None): node.value = value else: if( value < node.value ): if (node.left is None): node.left = Tree(value) else: node.left.create_node(value) elif( value > node.value ): if ( node.right is None): node.right = Tree(value) else: node.right.create_node(value) def find_height(node,Root): if (Root is None): return 0 else: l_subtree = node.find_height(Root.left) r_subtree= node.find_height(Root.right) return max(l_subtree,r_subtree)+1 def level_order(node,Root): height = node.find_height(Root) for i in range(0,height): node.traversal(Root,i) def traversal(node,Root,level): if Root==None: return elif level==0: print(Root.value,end = ' ') elif level >0: node.traversal(Root.left,level-1) node.traversal(Root.right,level-1) Root = Tree(5) Root.create_node(7) Root.create_node(2) Root.create_node(3) Root.create_node(6) Root.create_node(1) Root.create_node(8) print('Level order traversal :',end = '') Root.level_order(Root)
Output:
Level order traversal :5 2 7 1 3 6 8
I hope you have understood the code..!
Know more about tree traversal algorithms, Inorder traversal, Preorder traversal, Postorder traversal.
Thank you…😊
Leave a Reply