Tree: Postorder Traversal

  • + 10 comments

    My Java solution without recursion

    void postOrder(Node root) {
        Node t = root;
        Deque<Node> stack = new ArrayDeque<Node>();
        stack.push(root);
        while(!stack.isEmpty() && root!=null){
            root = stack.peek();
            //nodes without children should be printed 
            if( (root.left==null&&root.right==null) 
             || (t==root.left||t==root.right) ){//or nodes whose children have already been printed 
                System.out.print(root.data+" ");
                stack.pop();
                t = root;
            }else{
                if(root.right!=null) stack.push(root.right);
                if(root.left!=null) stack.push(root.left);
            }
        }
    }