# 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

Pingback: What is Level Order Traversal and implementation - Study Experts