## Introduction

Postorder traversal is a method for visiting all nodes in a binary tree. It follows a specific order: left subtree, right subtree, then root node. This "left-right-root" approach is useful in scenarios where child nodes must be processed before their parents, such as in tree deletion operations or evaluating mathematical expressions. This blog post will explain how postorder traversal works, and its implementation.

Unlike linear data structures (Array, Linked List, Queues, Stacks, etc.), which can only be traversed in one logical manner, trees can be traversed in various ways, which are:

**Depth-First Traversal:** In depth-first search (__DFS Algorithm__), the search tree is deepened as much as possible before going to the next sibling.

- Pre-order traversal (
*Root Left-Right*)

- In-order traversal (
*Left Root Right*)

- Postorder traversal (
*Left Right Root*)

**Breadth-First Traversal:** In Breadth-first search(BFS), the nodes are traversed in a level-wise order.

Although there is a possibility to perform a post-order traversal of the binary tree recursively, in this article we’ll be exploring post-order traversal using the Iterative approach, which will use stacks to perform the traversal of the tree.

Check out, Iterative Preorder Traversal of Binary Tree | Part 2

Before any further due, let’s get started:

## What is a Postorder Traversal in a Binary Tree?

A binary tree postorder traversal is a method of listing all of the tree's leaves and nodes so that for each node, all of its left children come before all of its right children, which come before the node itself. In simple words, Postorder traversal is a binary tree traversal approach in which you visit the left subtree first, then the right subtree, and finally the root.

`LeftSubtree -> RightSubtree -> Root`

Consider the following example of a binary tree traversal utilizing the post order.

In the preceding example, because the leftmost node is **A**, it is visited first. Following that, since **D** is the root node of **C** and **E**, the nodes **C** and **E** will be visited before the **D** node. The **B** node is now the last one to be visited in the left subtree. Now, the left subtree is visited, and because the algorithm expects the root to be visited last, it moves to the right subtree and processes each node in the same manner as it did for the left subtree.

Now that you are familiar with postorder traversal let’s look at the approaches we can perform to traverse a binary tree. As we are attempting to traverse the tree iteratively, thus we’ll be needing an **auxiliary** **stack** to process each node.

Must Read Recursive Binary Search.

# Example of Postorder Traversal

Let's consider a simple binary tree:

```
1
/ \
2 3
/ \
4 5
```

In postorder traversal, we visit the left subtree, then the right subtree, and finally the root node. Let's walk through this tree:

- Start at the root (1).
- Go to the left child (2).
- Go to its left child (4). It has no children, so we visit it. Output: 4
- Go back to 2, then to its right child (5). It has no children, so we visit it. Output: 4, 5
- We've finished both subtrees of 2, so we visit 2. Output: 4, 5, 2
- Go back to the root (1), then to its right child (3). It has no children, so we visit it. Output: 4, 5, 2, 3
- Finally, we've finished both subtrees of the root, so we visit the root (1).

**Final output:** 4, 5, 2, 3, 1

This order ensures that for any node, both its left and right subtrees are fully traversed before the node itself is visited.