Given a binary tree, the task is to write an **iterative** and **recursive** solution to perform **post-order traversal** on it.

##### Example 1: Print post-order traversal of a Binary Tree

Input:

**Output: **2, 5, 11, 6, 7, 5, 9, 9, 1

## Solutions

### Method 1: Iteration

The

**post-order**traversal of a binary tree can also be performed iteratively using "two"**Stack**.**Following is a simple stack-based iterative algorithm to perform post-order traversal:**if(root==null) return; s -> empty stack s.push(root) out -> empty stack while(not s.empty()) node -> s.pop() out.push(node) if(node.left !=null) node.push(node.left) if(node.right !=null) node.push(node.right) while(not out.empty()) node -> out.pop() visit(node)

##### Complexity

The time complexity of this solution is **O(n)** and space complexity is **O(n)** due to extra space required by stack.

### Method 2: Recursion

Post-order traversal of a tree using **recursion** is extremely simple and straightforward, its a three step code:

**1)** traverse, left of current-node

**2)** traverse, right of current-node

**3)** print current-node

if, current is null, return; this will make the **base condition** for this program.

if(root==null) return; preorder(root.left); preorder(root.right); visit(root);

##### Complexity

The time complexity of this solution is

**O(n)**and space complexity is**O(n)**due to recursive calls.