Inorder tree traversal in Python

Tree traversal means visiting each node of a tree data structure in a specific order. Tree traversals are classified based on the order in which the nodes are visited. Generally, there are two types of tree traversal( Depth-first and breadth-first). In this tutorial, we will learn the Inorder tree traversal which is one of the variants in depth-first search. As the name suggests, the depth-first search explores tree towards depth before visiting its sibling.

Let’s create the above binary tree to perform Inorder traversal.

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(3)
Root.create_node(2)
Root.create_node(6)
Root.create_node(1)
Root.create_node(7)
Root.create_node(4)
Root.create_node(9)
Root.create_node(8)

Inorder traversal using Recursion in Python

def Inorder( node, Root ): 
    if( Root is None ): 
        return
    node.Inorder(Root.left) 
    print(Root.value,end = ' ') 
    node.Inorder(Root.right)

• Traverse the left subtree recursively.
• Access the value of the current node.
• Traverse the right subtree recursively.

The order of the Inorder traversal is 1 2 3 4 5 6 7 8 9.
Note: If we traverse the left subtree first, then the parent node and the left subtree then such a traversal is called reverse inorder traversal.

Explanation:

• Firstly we created the Binary tree and performed Inorder traversal using recursive function.
• If the node is not empty, traverse the left subtree till the last node. Since the left child of the last node is None, the function will return and print the value in the last node. Similarly, the right child is also none.
• Print the value of the parent node of the left subtree and traverse to the right subtree.
• If the node is None return back to the parent node.

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 Inorder( node, Root ):

        if( Root is None ):
            return
        
        node.Inorder(Root.left)
        print(Root.value,end = ' ')
        node.Inorder(Root.right)

Root = Tree(5)
Root.create_node(3)
Root.create_node(2)
Root.create_node(6)
Root.create_node(1)
Root.create_node(7)
Root.create_node(4)
Root.create_node(9)
Root.create_node(8)
print('Inorder traversal :',end = '')
Root.Inorder(Root)

Output:

Inorder traversal :1 2 3 4 5 6 7 8 9

I hope you all have understood the algorithm..!
You can also read:

• Other variants of Depth-first search: Preorder traversal and Postorder traversal.
• Level order tree traversal ( BFS )