Binary Search Tree: Program to traverse using Postorder iterative approach

In this article, we will be going to write a program to Display the Postorder Traversal of a Binary Search Tree.
The Postorder of a Binary Search Tree: left subtree - right subtree - root

How to implement Postorder Traversal Iteratively

1. We achieve this order using two stacks.
2. We will add the nodes into the stack(in this case the second stack) in such a way that
   when we pop elements we will get the post order traversal pattern.
3. We push root node into first stack, pop it out, store it in temp node and push it into second stack.
   We then push temp's left node and then right node in first stack. Keep doing this till first stack is not empty.
4. After the first stack is empty, the second stack is filled with all the nodes in the order we want.
   We pop all the elements from second stack and print them.

Algorithm

1. Create two stack say nodeStack1 and nodeStack2.
2. If root is NULL then simply return.
3. Push root node into nodeStack1.
4. While nodeStack1 is not empty, pop one node from nodeStack1 and stored into temp,push temp into nodeStack2.
5. If temp.left is not NULL then push temp.left into nodeStack1.
6. If temp.right is not NULL then push temp.right into nodeStack1.
7. While nodeStack2 is not empty pop one node and stored into temp and print temp.data, which gives postorder

Complexity

Time Complexity : O(n) , where n is the number of nodes in binary search tree.
Auxiliary Space Complexity: O(n)

Java Code

import java.util.Stack;
 
    // A binary tree node
    class Node {
     
        int data;
        Node left, right;
     
        Node(int element) {
            data = element;
            left = right = null;
        }
    }
     
    class BinarySearchTree {
     
        Node Root;
     
        public void insert(int new_data) {
            Node temp, checker = null;
     
            temp = new Node(new_data);
            temp.left = temp.right = null;
            if (Root == null)
                Root = temp;
            else {
                checker = Root;
                while (true) {
                    if (temp.data > checker.data) {
     
                        if (checker.right == null) {
                            checker.right = temp;
                            checker = temp;
                            break;
                        } else {
                            checker = checker.right;
                        }
                    } else {
                        if (checker.left == null) {
                            checker.left = temp;
                            checker = temp;
                            break;
                        } else {
                            checker = checker.left;
                        }
                    }
                }
            }
        }
     
        public void iterativePostorder() {
     
            Stack nodeStack1 = new Stack();
            Stack nodeStack2 = new Stack();
     
            if (Root == null)
                return;
            
            nodeStack1.push(Root);
     
            while (!nodeStack1.isEmpty()) {
     
                Node temp = nodeStack1.pop();
                nodeStack2.push(temp);
     
                if (temp.left != null)
                    nodeStack1.push(temp.left);
                if (temp.right != null)
                    nodeStack1.push(temp.right);
            }
            while (!nodeStack2.isEmpty()) {
                Node temp = nodeStack2.pop();
                System.out.print(temp.data + " ");
            }
        }
     
        public static void main(String args[]) {
            BinarySearchTree tt = new BinarySearchTree();
            int[] bstElements = new int[] { 50, 20, 30, 10, 200, 70, 90 };
            int numberOfNodes = 7;
            for (int i = 0; i < numberOfNodes; i++) {
                tt.insert(bstElements[i]);
            }
            System.out.println("PostOrder OF Given Binary Search Tree");
            tt.iterativePostorder();
        }
    }

Output

PostOrder OF Given Binary Search Tree
10 30 20 90 70 200 50