// prefix traversal of tree

    public void printPre () {
        printPre (root);
        StdOut.println ();
    }
    private static void printPre (Node x) {
        if (x == null) return;

        StdOut.print (x.key + " ");
        printPre (x.left);
        printPre (x.right);
    }

    // depth first traversal of graph
    // mark when visiting
    public void printPre () {
        printPre (root, new HashSet<Node>());
        StdOut.println ();
    }
    private static void printPre (Node x, HashSet<Node> marked) {
        if (x == null || marked.contains (x)) return;
        marked.add (x);
        StdOut.print (x.key + " ");
        printPre (x.left, marked);
        printPre (x.right, marked);
    }