Post-order Tree Traversal - Iterative and Recursive

Posted by N.K. Chauhan on Mar 31, 2024

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.

Related


Pre-order Tree Traversal - Iterative and Recursive

Create a mirror tree from a given binary tree

Print Nodes in Top View of a Binary Tree

Print diagonal traversal of a binary tree

Find the diameter or width of a binary tree

Print a Binary Tree in Vertical Order

Print the left view of a binary tree

Write a program to print height/depth of a Binary Tree

In-order Tree Traversal - Iterative and Recursive

Print/Traverse a Binary Tree in Zigzag Order

Level Order or Breadth First traversal of Binary Tree