Sunday 12 April 2020

Algorithm for Postorder Tree Traversals : Iterative Model(Non-Recursive way)



import java.util.Stack;

//Postorder Tree Traversals : Iterative Model(Non-Recursive way)

class BinaryTreePostOrderTraversalIterativeModel {
     class TreeNode {
            TreeNode left, right;
            int data; // considering integer data.
      
            public TreeNode(int dataItem) {
                  this.data = dataItem;
                  left = null;
                  right = null;
            }
     }
      
      TreeNode root;
       BinaryTreePostOrderTraversalIterativeModel() {
             root = null;
       }
      
       void printPostOrderTraversal(TreeNode treeNode) {
             if(treeNode == null)
                    return;
            
             //Left, Right, Data
             Stack<TreeNode> s = new Stack<TreeNode>();
             s.push(root);

             while (!s.isEmpty()) {
                    TreeNode current = s.peek();

                    if ( current.left == null || current.right == null) {
                          TreeNode node = s.pop();
                          System.out.println(node.data);
                    } else {
                          if(current.right != null){
                                 s.push(current.right);
                                 current.right = null;
                          }
                          if(current.left != null){
                                 s.push(current.left);
                                 current.left = null;
                          }
                    }
             }
       }
      
       void printPostOrder() {
             printPostOrderTraversal(root);
       }

       public static void main(String[] args) {
             BinaryTreePostOrderTraversalIterativeModel tree = new BinaryTreePostOrderTraversalIterativeModel();
        tree.root = new TreeNode(1);
       
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
       
        tree.root.left.left = new TreeNode(4);
        tree.root.left.right = new TreeNode(5);
       
        tree.root.right.left = new TreeNode(6);
        tree.root.right.right = new TreeNode(7);
       
        tree.printPostOrder();
       }

}

//Time Complexity: O(n). Space Complexity: O(n).


Thanks..!!

No comments:

Post a Comment