Inorder Tree Traversal in Python
Inorder tree traversal is basically traversing the left, root, and right node of each sub-tree. We can understand it better by using below algorithm:
- Traverse the left subtree by recursively calling the inorder traversal function.
- Visit the root node (usually an action is performed such as printing the node value).
- Traverse the right subtree by recursively calling the inorder traversal function.
Example
The Node class represents an individual node of the tree, where each node has a left child, a right child, and a data value. The printInorder function recursively traverses the tree in an inorder manner: it first traverses the left subtree, then visits the current node to print its data value, and finally traverses the right subtree. In the driver code section (if __name__ == "__main__":), a sample binary tree with seven nodes is constructed and the printInorder function is called to display the inorder traversal of the tree. The output would be the values of the nodes in the order they are visited using the inorder traversal method.
Python3
# Python3 code to implement the approach# Class describing a node of treeclass Node: def __init__(self, v): self.left = None self.right = None self.data = v# Inorder Traversaldef printInorder(root): if root: # Traverse left subtree printInorder(root.left) # Visit node print(root.data,end=" ") # Traverse right subtree printInorder(root.right)if __name__ == "__main__": # Build the tree root = Node(10) root.left = Node(25) root.right = Node(30) root.left.left = Node(20) root.left.right = Node(35) root.right.left = Node(15) root.right.right = Node(45) # Function call print("Inorder Traversal:",end=" ") printInorder(root) |
Inorder Traversal: 20 25 35 10 15 30 45
Tree Traversal Techniques in Python
A tree is a non-linear data structure or we can say that it is a type of hierarchical structure. It is like an inverted tree where roots are present at the top and leaf or child nodes are present at the bottom of the tree. The root node and its child nodes are connected through the edges like the branches in the tree. In this article, we will learn different ways of traversing a tree in Python.
Prerequisites for Tree Traversal in Python
- Basics of Classes and Objectes in Python.
- Basics of Tree Data structure.
Contact Us