What is post-order traversal and implementation

In this blog, we would discuss What is post-order traversal and implementation. In computer science, post-order tree traversal is a type of depth-first search. It is also known as a postfix traversal or postorder tree traversal.

 

 

 

What is post-order traversal?

 

Post order traversal is a type of tree traversal algorithm that visits each node in a tree after its left and right child nodes have been visited. This type of traversal is typically used to delete nodes from a tree or to print out a tree’s contents in reverse order. There are several reasons why you might want to use post-order traversal. For example, if you want to delete all the nodes in a tree, you can use post-order traversal to visit each node and delete it after its children have been deleted. Another reason to use post-order traversal is to print out a tree’s contents in reverse order.

 

 

This can be useful if you want to reverse the order of a list that is stored in a tree. There are many ways to implement post-order traversal. One way is to use a stack. You can push each node onto the stack as you visit it. Then, when you reach a leaf node, you can pop the nodes off the stack and print them out. Another way to implement post-order traversal is to use a queue. You can enqueue each node as you visit it. Then, when you reach a leaf node, you can dequeue the nodes and print them out.

 

 

The algorithm for post-order tree traversal is as follows:

 

 

• Start at the root node.

 

• Traverse the left subtree.

 

• Traverse the right subtree.

 

• Visit the root node.

 

 

A post-order traversal is a type of traversal where the nodes are processed after their children.

 

 

This is in contrast to a pre-order traversal, where the nodes are processed before their children. Post-order traversals are often used when the goal is to process the entire tree, or when the order in which the nodes are processed doesn’t matter. For example, a post-order traversal of a binary tree will visit the left child, then the right child, and finally the root node.

 

 

 

 

Implementation of post-order Traversal

 

class Node:

    def __init__(self, key):

        self.left = None

        self.right = None

        self.val = key


def printPostorder(root):

    if root:

        printPostorder(root.left)

        printPostorder(root.right)

        print(root.val)




root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)




print("Postorder traversal of binary tree is")

printPostorder(root)

 

Output

 

 

 

 

Uses of Post-order Traversal

 

One common use for a post-order traversal is to calculate the depth of each node. This can be done by first processing all of the child nodes, and then adding 1 to the depth of the current node. Another common use for a post-order traversal is to delete all of the nodes in a tree. This can be done by first deleting the child nodes, and then the current node.

 

 

Post-order traversals can also be used to calculate the size of a tree. This is done by first calculating the size of the left subtree, then the size of the right subtree, and finally adding 1 for the root node.

 

 

One common use of post-order traversal is to delete a tree or subtree. This is because all children of a node must be deleted before the node itself can be deleted.

 

 

Another use is to create a copy of a tree. This can be done by first creating copies of all the children of the root node, and then creating a copy of the root node itself.

 

 

Also, read  – What is filter Function and its Implementation