// prefix order traversal of a tree

    public void printPrefix () {
        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 ();
    }

    // depth first traversal of a graph
    // mark when enqueuing
    public void printPrefix () {
        Stack<Node> s = new Stack<> ();
        HashSet<Node> marked = new HashSet<> ();
        s.push (root); marked.add (root);
        while (!s.isEmpty ()) {
            Node x = s.pop ();
            if (x == null || marked.contains (x)) continue;
            StdOut.print (x.key + " ");
            s.push (x.right); marked.add (x.right)
            s.push (x.left);  marked.add (x.left)
        }
        StdOut.println ();
    }