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 Traversaldef 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 codeif __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
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