Iterative Postorder Traversal | Set 1 (Using Two Stacks) - GeeksforGeeks

Iterative Postorder Traversal | Set 1 (Using Two Stacks) - GeeksforGeeks
Also check LeetCode - Binary Tree Postorder Traversal
The postorder traversal can easily be done using two stacks though. The idea is to push reverse postorder traversal to a stack. Once we have reverse postorder traversal in a stack, we can just pop all items one by one from the stack and print them, this order of printing will be in postorder because of LIFO property of stacks. Now the question is, how to get reverse post order elements in a stack – the other stack is used for this purpose. For example, in the following tree, we need to get 1, 3, 7, 6, 2, 5, 4 in a stack. If take a closer look at this sequence, we can observe that this sequence is very similar to preorder traversal. The only difference is right child is visited before left child and therefore sequence is “root right left” instead of “root left 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

def postOrderIterative(root):

     

    # Create two stacks 

    s1 = []

    s2 = []

     

    # Push root to first stack

    s1.append(root)

     

    # Run while first stack is not empty

    while(len(s1) >0):

         

        # Pop an item from s1 and append it to s2

        node = s1.pop()

        s2.append(node)

     

        # Push left and right children of removed item to s1

        if node.left is not None:

            s1.append(node.left)

        if node.right is not None :

            s1.append(node.right)



        # Print all eleements of second stack

    while(len(s2) > 0):

        node = s2.pop()

        print node.data,

http://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/

    static Node root;

    ArrayList<Integer> list = new ArrayList<Integer>();



    // An iterative function to do postorder traversal of a given binary tree

    ArrayList<Integer> postOrderIterative(Node node) {

        Stack<Node> S = new Stack<Node>();

         

        // Check for empty tree

        if (node == null) {

            return list;

        }

        S.push(node);

        Node prev = null;

        while (!S.isEmpty()) {

            Node current = S.peek();



            /* go down the tree in search of a leaf an if so process it and pop

            stack otherwise move down */

            if (prev == null || prev.left == current || prev.right == current) {

                if (current.left != null) {

                    S.push(current.left);

                } else if (current.right != null) {

                    S.push(current.right);

                } else {

                    S.pop();

                    list.add(current.data);

                }



                /* go up the tree from left node, if the child is right 

                push it onto stack otherwise process parent and pop stack */

            } else if (current.left == prev) {

                if (current.right != null) {

                    S.push(current.right);

                } else {

                    S.pop();

                    list.add(current.data);

                }

                 

                /* go up the tree from right node and after coming back

                 from right node process parent and pop stack */

            } else if (current.right == prev) {

                S.pop();

                list.add(current.data);

            }



            prev = current;

        }



        return list;

    }

http://www.geeksforgeeks.org/iterative-preorder-traversal/

Given a Binary Tree, write an iterative function to print Preorder traversal of the given binary tree.

Refer this for recursive preorder traversal of Binary Tree. To convert an inherently recursive procedures to iterative, we need an explicit stack. Following is a simple stack based iterative process to print Preorder traversal.
1) Create an empty stack nodeStack and push root node to stack.
2) Do following while nodeStack is not empty.
….a) Pop an item from stack and print it.
….b) Push right child of popped item to stack
….c) Push left child of popped item to stack

    Node root;

     

    void iterativePreorder()

    {

        iterativePreorder(root);

    }

 

    // An iterative process to print preorder traversal of Binary tree

    void iterativePreorder(Node node) {

         

        // Base Case

        if (node == null) {

            return;

        }

 

        // Create an empty stack and push root to it

        Stack<Node> nodeStack = new Stack<Node>();

        nodeStack.push(root);

 

        /* Pop all items one by one. Do following for every popped item

         a) print it

         b) push its right child

         c) push its left child

         Note that right child is pushed first so that left is processed first */

        while (nodeStack.empty() == false) {

             

            // Pop the top item from stack and print it

            Node mynode = nodeStack.peek();

            System.out.print(mynode.data + " ");

            nodeStack.pop();

 

            // Push right and left children of the popped node to stack

            if (mynode.right != null) {

                nodeStack.push(mynode.right);

            }

            if (mynode.left != null) {

                nodeStack.push(mynode.left);

            }

        }

    }

Read full article from Iterative Postorder Traversal | Set 1 (Using Two Stacks) - GeeksforGeeks