//postorder recursion
    public static void PostOrder(Node r) {
        if( r != null) {
            PostOrder(r.left);
            PostOrder(r.right);
            System.out.println("[" + r.data + "]");
        }
    }

//Postorder with two stacks
    public static void PostorderTwoStacks(Node curr) {
        Stack<Node> st1 = new Stack<Node>();
        Stack<Node> st2 = new Stack<Node>();
        if(curr != null) {
            st1.push(curr);
            while(!st1.empty()) {
                Node node = st1.pop();
                st2.push(node);
                if(node.left != null)
                    st1.push(node.left);
                if(node.right != null)
                    st1.push(node.right);
            }
            while(!st2.empty()) {
                Node node = st2.pop();
                System.out.println("Two Stacks Iteration["+node.data+"]");
            }
        }
    }

// postorder with iteration
    public static void postIteration(Node root) {
        Stack<Node> stack = new Stack<Node>();
        Node curr = root;
        while(curr != null || stack.isEmpty() == false) {
            if(curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                Node node = stack.peek();
                if(node.isVisited) {
                    System.out.println("[" + node.data + "]");
                    stack.pop();
                } else {
                    node.isVisited = true;
                    curr = node.right;
                }
            }
        }
    }

public static void preorder(Node root) {
        if(root != null) {
            System.out.println("[" + root.data + "]");
            inorder(root.left);
            inorder(root.right);
        }
    }
    public static void inorder(Node root) {
        if(root != null) {
            inorder(root.left);
            System.out.println("[" + root.data + "]");
            inorder(root.right);
        }
    }

    public static void preorderIteration(Node r) {
        Stack<Node> st = new Stack<Node>();
        Node curr = r;
        if( curr != null) {
            while(curr != null || !st.empty()) {
                if(curr != null) {
                    System.out.println("["+curr.data+"]");
                    st.push(curr);
                    curr = curr.left;
                } else {
                    Node node = st.pop();
                    curr = node.right;
                }
            }
        }
        curr = r;
    }

    public static void inorderIteration(Node r) {
        Stack<Node> st = new Stack<Node>();
        Node curr = r;
        if( curr != null) {
            while(curr != null || !st.empty()) {
                if(curr != null) {
                    st.push(curr);
                    curr = curr.left;
                } else {
                    Node node = st.pop();
                    System.out.println("["+curr.data+"]");
                    curr = node.right;
                }
            }
        }
        curr = r;
    }

class InorderIterator {
    Node curr;
    Stack<Node> stack = new Stack<Node>();
    public InorderIterator(Node r) {
        this.curr = r;
    }
    public boolean hasNext() {
        if(curr != null || stack.size() > 0)
            return true;
        else
            return false;
    }
    public int next() {
        while(hasNext()) {
            if(curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                Node node = stack.pop();
                curr = node.right;
                return node.data;
            }
        }
        return -1;
    }
}