Iterative Postorder Traversal of a Binary Tree

Iterative Postorder Traversal of a Binary Tree

• Visit all the nodes in the left subtree

• Visit all the nodes in the right subtree

• Visit the root node
  

	public void preOrder() {
		if (root == null) {
			return;
		}

		Stack<TreeNode> stack = new Stack<>();
		stack.push(root);

		while (!stack.isEmpty()) {
			TreeNode temp = stack.pop();
			System.out.print(temp.data + " ");
			if (temp.right != null) {
				stack.push(temp.right);
			}
			if (temp.left != null) {
				stack.push(temp.left);
			}
		}
	}

First, we create a TreeNode name current that current simply points to the root node. We create a Stack Data Structure to traverse this binary tree using post-order traversal from the root node by pushing it into a Stack and then using a while loop and providing the two conditions first is the current is not null or stack is not empty. If any of these conditions comes out to be true then the while loop will be executed.

In the first step, we are checking is that if the current is not equal to null, then we simply go inside the if condition and execute the code.
Otherwise, our current points to null then if condition comes out to be false then else condition will be executed.

Our else block first we create a temporary variable name temp and we assign a value stack.peek().right.
Inside the else block we are creating two conditions if the temp is null then if block comes out to be true after that poll the value in the stack and print the value. Between if block using while loop and checking the stack is not empty (so, as we have recently pulled an element out of it, so there could be a chance at the stack becomes empty) and check temp equals to stack.peek().right if two conditions are true then the while loop will be executed. Simply poll the value in the stack and assign it temp and print the value. Otherwise, our temp is not equal to null then if the condition comes out to be false then else condition will be executed simply temp assign it current.

Why used stack data structure? Because we know Stack is a LIFO (last in first out) data structure and as per post-order traversal, we need to explore the left subtree before the right subtree.

import java.util.Stack;

public class BinaryTree {

	private TreeNode root; // instance variable
	// inner class start

	private class TreeNode { // inner class
		private TreeNode left;
		private TreeNode right;
		private int data;

		public TreeNode(int data) { // inner class Constructor
			this.data = data;
		}
	}

	public void createTree() { // create tree method
		TreeNode first = new TreeNode(12);
		TreeNode second = new TreeNode(8);
		TreeNode third = new TreeNode(9);
		TreeNode fourth = new TreeNode(4);
		TreeNode fifth = new TreeNode(3);

		root = first;
		first.left = second;
		first.right = third;
		second.left = fourth;
		second.right = fifth;
	}

	public void preOrder() {
		if (root == null) {
			return;
		}

		Stack<TreeNode> stack = new Stack<>();
		stack.push(root);

		while (!stack.isEmpty()) {
			TreeNode temp = stack.pop();
			System.out.print(temp.data + " ");
			if (temp.right != null) {
				stack.push(temp.right);
			}
			if (temp.left != null) {
				stack.push(temp.left);
			}
		}
	}

	public static void main(String[] args) { // main method
		BinaryTree binary = new BinaryTree(); // crate tree object
		binary.createTree(); // called createTree() method
		binary.preOrder(); // called preOrder method passing root

	}

}

Output

12 8 4 3 9