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.
Different Types of Tree Traversal Techniques
There are three types of tree traversal techniques:
- Inorder Traversal in Tree
- Preorder Traversal in Tree
- Postorder Traversal in Tree
Note: These traversal in trees are types of depth first search.
Overview of Tree Traversal Techniques
In the below image we can see a binary tree and the result of each traversal technique. We will be going to understand each technique in detail.
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 tree class Node: def __init__( self , v): self .left = None self .right = None self .data = v # Inorder Traversal def 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
Pre-Order Tree Traversal in Python
Pre-order tree traversal is basically traversing the Root, Left, and Right node of each sub-tree. We can understand it better by using below algorithm:
- Visit the root node.
- Traverse the left subtree by recursively calling the preorder traversal function.
- Traverse the right subtree by recursively calling the preorder traversal function.
Example:
The given code defines a binary tree and demonstrates the preorder traversal technique. The `Node` class defines each node of the tree with attributes for its data, left child, and right child. The `printPreOrder` function carries out a recursive preorder traversal, which involves: first visiting and printing the current node’s data, then traversing the left subtree, followed by traversing the right subtree. In the driver code, a sample binary tree is constructed with nodes having values ranging from 10 to 300. The function `printPreOrder` is then invoked on the root of this tree, printing the nodes in the order dictated by the preorder traversal.
Python3
class Node: def __init__( self , v): self .data = v self .left = None self .right = None # Preorder Traversal def printPreOrder(node): if node is None : return # Visit Node print (node.data, end = " " ) # Traverse left subtree printPreOrder(node.left) # Traverse right subtree printPreOrder(node.right) # Driver code if __name__ = = "__main__" : # Build the tree root = Node( 95 ) root.left = Node( 15 ) root.right = Node( 220 ) root.left.left = Node( 10 ) root.left.right = Node( 30 ) root.right.left = Node( 160 ) root.right.right = Node( 285 ) # Function call print ( "Preorder Traversal: " , end = "") printPreOrder(root) |
Preorder Traversal: 95 15 10 30 220 160 285
Post-Order Tree Traversal using Python
Post-order tree traversal is basically traversing the Left, Right, and Root node of each sub-tree. We can understand it better by using below algorithm:
- Traverse the left subtree by recursively calling the postorder traversal function.
- Traverse the right subtree by recursively calling the postorder traversal function.
- Visit the root node.
Example:
The provided code showcases the postorder traversal method for a binary tree. The `Node` class represents a node in the tree, characterized by its data, left child, and right child. The `printPostOrder` function conducts a recursive postorder traversal on the tree. In this traversal, the left subtree is traversed first, followed by the right subtree, and then the current node’s data is visited and printed. This sequence ensures that a node is processed after both its left and right subtrees have been traversed (hence, “postorder”). The driver code constructs a sample binary tree and subsequently calls the `printPostOrder` function to display the result of the postorder traversal of the tree. The nodes’ values will be printed in the sequence dictated by the postorder traversal technique.
Python3
class Node: def __init__( self , v): self .data = v self .left = None self .right = None # Preorder Traversal def printPostOrder(node): if node is None : return # Traverse left subtree printPostOrder(node.left) # Traverse right subtree printPostOrder(node.right) # Visit Node print (node.data, end = " " ) # Driver code if __name__ = = "__main__" : # Build the tree root = Node( 10 ) root.left = Node( 2 ) root.right = Node( 20 ) root.left.left = Node( 1 ) root.left.right = Node( 3 ) root.right.left = Node( 15 ) root.right.right = Node( 30 ) # Function call print ( "Postorder Traversal: " , end = "") printPostOrder(root) |
Postorder Traversal: 1 3 2 15 30 20 10
Contact Us