// recursive version

    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);
    }

    // iterative version

    public void printPre () {
        Stack<Node> s = new Stack<> ();
        s.push (root);
        while (!s.isEmpty ()) {
            Node x = s.pop ();
            if (x == null) continue;

            StdOut.print (x.key + " ");
            s.push (x.right);
            s.push (x.left);
        }
        StdOut.println ();
    }