Post order Traversal- Binary Tree in java

Information about Tree : Tree Introduction
Pre-Order Traversal in Binary Tree

Post Order Traversal in Binary Tree: In Post order(Post fix), First we traversal through children(left to right manner) before traversing parent.

1. Traverse the left subtree by recursively calling the post-order function.
2. Traverse the right subtree by recursively calling the post-order function.
3. Display the data part of root element (or current element).

In the above Tree, before traversing 1, we have to traverse 2 and 3, and before traversing 2 we have to traversal 5 and 6. Same rule applies on all the node of tree. So Leftmost child would be traversed first and root node would be traversed at last.

Output: 9,5,6,2,8,410,7,3,1



Recursive Way:


 public void postOrderRecusriveWay(BinaryDataTree<Integer> root) {
   if (root == null) {
            return;
       }
     postOrderRecusriveWay(root.getLeft());
    postOrderRecusriveWay(root.getRight());
   System.out.print(root.getData() + " ");
}


 Iterative Way:

public void postOrderIterativeWay(BinaryDataTree<Integer> root) {

        Stack<BinaryDataTree<Integer>> s = new Stack<BinaryDataTree<Integer>>();
        if (root == null)
            return;

        while (true) {
            while (root != null) {
                s.push(root);
                root = root.getLeft();
            }
            if (s.isEmpty())
                return;
            root = s.peek().getRight();
            if (root == null) {
                root = s.pop();
                System.out.print(root.getData() + " ");
                while (!s.isEmpty() && root == s.peek().getRight()) {
                    root = s.pop();
                    System.out.print(root.getData() + " ");
                }
                root = null;

            }
        }
    }