// Binary.java

// a node in a tree has data, and a left and right subtree
class Node {
    int data;
    Node left;
    Node right;
}

public class Binary {
    // a pre-order tree traversal
    public static void preorder(Node node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preorder(node.left);
            preorder(node.right);
        }
    }

    // an in-order tree traversal
    public static void inorder(Node node) {
        if (node != null) {
            inorder(node.left);
            System.out.print(node.data + " ");
            inorder(node.right);
        }
    }

    // a post-order tree traversal
    public static void postorder(Node node) {
        if (node != null) {
            postorder(node.left);
            postorder(node.right);
            System.out.print(node.data + " ");
        }
    }

    public static void main(String args[]) {
        // construct a tree manually
        //           56
        //       88      16 
        //     72  44  99  6

        // make a root node
        Node root = new Node();
        root.data = 56;

        // left side
        root.left = new Node();
        root.left.data = 88;
        root.left.left = new Node();
        root.left.left.data = 72;
        root.left.left.left = null;
        root.left.left.right = null;
        root.left.right = new Node();
        root.left.right.data = 44;
        root.left.right.left = null;
        root.left.right.right = null;

        // right side
        root.right = new Node();
        root.right.data = 16;
        root.right.left = new Node();
        root.right.left.data = 99;
        root.right.left.left = null;
        root.right.left.right = null;
        root.right.right = new Node();
        root.right.right.data = 6;
        root.right.right.left = null;
        root.right.right.right = null;
        
        // print out the traversals
        System.out.print("Pre: ");
        preorder(root);

        System.out.print("\nIn: ");
        inorder(root);

        System.out.print("\nPost: ");
        postorder(root);
        System.out.print("\n");
    }
}