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.