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