DSA Post-order Traversal

DSA Post-order Traversal – Complete Beginner Guide

(Concept • Steps • Example • Code • Complexity)

Post-order Traversal is a Depth-First Search (DFS) technique used to traverse Binary Trees.
It is especially useful when children must be processed before the parent.

1️⃣ What is Post-order Traversal?

In Post-order Traversal, nodes are visited in this order:

Left → Right → Root
The root node is visited last.

2️⃣ Easy Way to Remember

So:

3️⃣ Post-order Traversal – Step by Step

Example Binary Tree

Traversal Steps

Go left → 4
Go right → 5
Visit parent → 2
Visit right subtree → 3
Visit root → 1

Output

4️⃣ Post-order Traversal Algorithm

Traverse left subtree
Traverse right subtree
Visit root node

5️⃣ Pseudocode

6️⃣ Post-order Traversal – Recursive Code (C++)

7️⃣ Complete Example Program (C++)

#include <iostream>
using namespace std;struct Node {
int data;
Node* left;
Node* right;
};

Node* newNode(int value) {
Node* node = new Node();
node->data = value;
node->left = node->right = NULL;
return node;
}

void postorder(Node* root) {
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
}

int main() {
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

postorder(root);
return 0;
}

#include <iostream>

using namespace std;struct Node {

int data;

Node* left;

Node* right;

};

Node* newNode(int value) {

Node* node = new Node();

node->data = value;

node->left = node->right = NULL;

return node;

}

void postorder(Node* root) {

if (root == NULL) return;

postorder(root->left);

postorder(root->right);

cout << root->data << " ";

}

int main() {

Node* root = newNode(1);

root->left = newNode(2);

root->right = newNode(3);

root->left->left = newNode(4);

root->left->right = newNode(5);

postorder(root);

return 0;

}

Output

8️⃣ Iterative Post-order Traversal

(Using Two Stacks – Easy to Understand)

#include <stack>

void postorderIterative(Node* root) {
if (root == NULL) return;

stack<Node*> s1, s2;
s1.push(root);

while (!s1.empty()) {
Node* curr = s1.top();
s1.pop();
s2.push(curr);

if (curr->left) s1.push(curr->left);
if (curr->right) s1.push(curr->right);
}

while (!s2.empty()) {
cout << s2.top()->data << " ";
s2.pop();
}
}

#include <stack>

void postorderIterative(Node* root) {

if (root == NULL) return;

stack<Node*> s1, s2;

s1.push(root);

while (!s1.empty()) {

Node* curr = s1.top();

s1.pop();

s2.push(curr);

if (curr->left) s1.push(curr->left);

if (curr->right) s1.push(curr->right);

}

while (!s2.empty()) {

cout << s2.top()->data << " ";

s2.pop();

}

9️⃣ Time & Space Complexity

Time Complexity

Space Complexity

Recursive: O(h)
Iterative: O(n)
(h = height of tree)

🔟 Where is Post-order Traversal Used?

✔ Deleting a tree
✔ Evaluating expression trees
✔ Freeing memory
✔ Bottom-up processing

1️⃣1️⃣ Traversal Comparison

Traversal	Order
Pre-order	Root → Left → Right
In-order	Left → Root → Right
Post-order	Left → Right → Root

Interview Questions (Post-order)

Q1. Why root is visiting last in post-order?
👉 Children must be processed first

Q2. Which traversal is using to delete a tree?
👉 Post-order

Q3. Can post-order be iterative?
👉 Yes, using stacks

Final Summary

✔ Post-order traversal visits root last
✔ Order: Left → Right → Root
✔ Ideal for bottom-up problems
✔ Time complexity: O(n)
✔ Very important for tree operations

DSA Post-order Traversal