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…😊