Postorder tree traversal in Python
In this tutorial, we will learn about the Postorder traversal of a tree data structure in Python. It is one of the three variants of the Depth-first search. Postorder tree traversal is also known as the LRN algorithm (Left, Right, Node). In the previous tutorials, I have also explained about Inorder traversal and Preorder traversal in Python, which are the other two variants of DFS.
Let’s create a binary tree and learn to implement this algorithm. Since we are using the recursive method to traverse the tree, I recommend you to get familiar with recursion.
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(7) Root.create_node(2) Root.create_node(3) Root.create_node(6) Root.create_node(1) Root.create_node(8)
Postorder traversal of a Tree in Python
def Postorder( node, Root ): if( Root is None ): return node.Postorder(Root.left) node.Postorder(Root.right) print(Root.value,end = ' ')
- Traverse the left subtree recursively.
- Traverse the right subtree recursively.
- Access the value of the current node.
The order of the Postorder traversal is 1 3 2 6 8 7 5.
Explanation:
- Firstly we created a binary tree with eight nodes and traversed using a postorder tree traversal algorithm.
- If the node is None, the control will return back to the calling function. Since we created a binary tree, the node is not None. As a result, we traverse the left subtree and the last left node value is printed. After that, we traverse the right subtree and print the values. At last, the parent node is printed.
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 Postorder( node, Root ): if( Root is None ): return node.Postorder(Root.left) node.Postorder(Root.right) print(Root.value,end = ' ') Root = Tree(5) Root.create_node(7) Root.create_node(2) Root.create_node(3) Root.create_node(6) Root.create_node(1) Root.create_node(8) print('Postorder traversal :',end = '') Root.Postorder(Root)
Output:
Level order traversal :1 3 2 6 8 7 5
If you have any quires, please drop in your comments.
Thank you…😊
thanks for the post. Learned something new from it.
Thanks for the feedback 🙂