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…😊

One response to “Postorder tree traversal in Python”

1. ekhe says:

   May 14, 2020 at 2:45 am

   thanks for the post. Learned something new from it.

   Reply