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 )
node.Inorder(Root.left)
print(Root.value,end = ‘ ‘)
node.Inorder(Root.right)
Can you explain how automatically it skip the first line here and print the Root.value, In case of None?
Good question but haven’t worked with traversals using Python enough to give an accurate answer, but certainly will do the research.