import java.util.*;

public class Main {
    public static void main(String[] args) {
        //         1
        //      2     3
        //    4   5     6
        Node root = new Node(1);
        Node n11 = new Node(2);
        Node n12 = new Node(3);
        Node n21 = new Node(4);
        Node n22 = new Node(5);
        Node n23 = new Node(6);
        root.left = n11;
        root.right = n12;
        n11.left = n21;
        n11.right = n22;
        n12.right = n23;
        inOrder(root);
        preOrder(root);
        postOrder(root);
        postOrderAlter(root);
    }

    public static void inOrder(Node root) {
        Stack<Node> stack = new Stack<>();
        Node curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left; // Traversal left
            }
            curr = stack.pop(); // Do sth on root
            System.out.printf("%d\t", curr.val);
            if (curr != null) {
                curr = curr.right; // Traversal right
            }
        }
        System.out.println();
    }

    public static void preOrder(Node root) {
        Stack<Node> stack = new Stack<>();
        Node curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                System.out.printf("%d\t", curr.val);
                stack.push(curr);
                curr = curr.left;
            }
            if (!stack.isEmpty()) {
                curr = stack.pop();
                curr = curr.right;
            }
        }
        System.out.println();
    }

    public static void postOrder(Node root) {
        Stack<Node> stack = new Stack<>();
        Stack<Node> reverse = new Stack<>();
        Node curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                reverse.push(curr);
                curr = curr.right;
            }
            if (!stack.isEmpty()) {
                curr = stack.pop();
                curr = curr.left;
            }
        }
        while (!reverse.isEmpty()) {
            System.out.printf("%d\t", reverse.pop().val);
        }
        System.out.println();
    }

    public static void postOrderAlter(Node root) {
        Stack<Node> stack = new Stack<>();
        if (root != null) stack.push(root);
        Node curr = null;
        Node prev = null;
        while (!stack.isEmpty()) {
            curr = stack.peek();
            if (prev == null || prev.left == curr || prev.right == curr) {
                if (curr.left != null) {
                    stack.push(curr.left);
                } else if (curr.right != null) {
                    stack.push(curr.right);
                }
            } else if (curr.left == prev) {
                if (curr.right != null) {
                    stack.push(curr.right);
                }
            } else {
                System.out.printf("%d\t", curr.val);
                stack.pop();
            }
            prev = curr;
        }
        System.out.println();
    }
}

class Node {
    int val;
    Node left;
    Node right;

    public Node(int val) {
        this.val = val;
    }
}