Tree Traversal | Iterative Program - Stack

 
import java.util.Stack;

class BinaryTree {
    private static Node root;
    
    /**
     *  a) print it
     *  b) push its right child
     *  c) push its left child
     */
    void preOrder(Node root) {
        if(root != null) {
            Stack stack = new Stack<>();
            Node current;
            stack.push(root);
            while(!stack.empty()){
                // Pop the top item from stack and print it
                current = stack.pop();
                System.out.print(current.data + " ");
                // Push right and left children of the popped node to stack
                if(current.right != null) {
                    stack.push(current.right);
                }
                if(current.left != null) {
                    stack.push(current.left);
                }
            }
        }
    }
    
    void inOrder(Node root) {
        if(root == null) {
            return;
        }
        Stack stack = new Stack<>();
        // start from the root node (set current node to the root node)
        Node current = root;
        // if the current node is null and the stack is also empty, we are done
        while(current != null || !stack.empty()) {
            // if the current node exists, push it into the stack (defer it)
            // and move to its left child
            if(current != null) {
                stack.push(current);
                current = current.left;
            } else {
                current = stack.pop();
                System.out.print(current.data + " ");
                current = current.right;
            }
        }
    }
    
    /**
     * 1. Push root to first stack.
     * 2. Loop while first stack is not empty
     * 2.1 Pop a node from first stack and push it to second stack
     * 2.2 Push left and right children of the popped node to first stack
     * 3. Print contents of second stack
     */
    void postOrderUsingTwoStacks(Node root) {
        if(root == null) {
            return;
        }
        // create an empty stack and push the root node
        Stack stack = new Stack<>();
        stack.push(root);
    
        // create another stack to store postorder traversal
        Stack out = new Stack<>();
    
        // loop till stack is empty
        while (!stack.empty()) {
            // pop a node from the stack and push the data into the output stack
            Node curr = stack.pop();
            out.push(curr.data);
    
            // push the left and right child of the popped node into the stack
            if (curr.left != null) {
                stack.push(curr.left);
            }
    
            if (curr.right != null) {
                stack.push(curr.right);
            }
        }
    
        // print postorder traversal
        while (!out.empty()) {
            System.out.print(out.pop() + " ");
        }
    }
    
    /**
     * 1.1 Create an empty stack
    * 2.1 Do following while root is not NULL
        * a) Push root's right child and then root to stack.
        * b) Set root as root's left child.
    * 2.2 Pop an item from stack and set it as root.
        * a) If the popped item has a right child and the right child 
        *    is at top of stack, then remove the right child from stack,
        *    push the root back and set root as root's right child.
        * b) Else print root's data and set root as NULL.
    * 2.3 Repeat steps 2.1 and 2.2 while stack is not empty.
    */
    void postOrderUsingOneStack(Node root) {
        if(root == null) {
            return;
        }
        Stack stack = new Stack<>();
        Node current = root;
        do {
            while(current != null) {
                if(current.right != null) {
                    stack.push(current.right);
                }
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            if(current.right != null && !stack.empty() && current.right == stack.peek()) {
                Node temp = stack.pop();
                stack.push(current);
                current = temp;
            } else {
                System.out.print(current.data + " ");
                current = null;
            }
        } while(!stack.empty());
    }
    
    Node populateTree() {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        return root;
    }
    
	public static void main (String[] args) {
		BinaryTree tree = new BinaryTree();
		root = tree.populateTree();
        
        System.out.println("Pre order :");
        tree.preOrder(root);
        System.out.println("\nIn order :");
        tree.inOrder(root);
        System.out.println("\nPost order using 2 stacks :");
        tree.postOrderUsingTwoStacks(root);
        System.out.println("\nPost order using 1 stacks :");
        tree.postOrderUsingOneStack(root);
	}
	private static class Node {
	    Node left;
	    int data;
	    Node right;
	    public Node(int data) {
	        this.data = data;
	    }
	}
}

 
Output
Pre order :
1 2 4 5 3 6 7 
In order :
4 2 5 1 6 3 7 
Post order using 2 stacks :
4 5 2 6 7 3 1 
Post order using 1 stacks :
4 5 2 6 7 3 1