import java.util.Iterator;
import java.util.concurrent.atomic.AtomicReference;
import java.util.function.Consumer;

public class BST <E extends Comparable<E> > implements Iterable<E> {
    private Node root;
    private class Node {
        E elem;
        Node left, right;
        Node (E elem) {
            this.elem=elem;
        }
    }
    public void add (E elem) {
        root = add (root, elem);
    }
    private Node add (Node node, E elem) {
        if (node == null) return new Node(elem);
        int s = elem.compareTo(node.elem);
        if (s<0) {
            node.left = add(node.left, elem);
        } else if (s>0) {
            node.right = add(node.right, elem);
        }
        return node;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            class Stack {
                Node node;
                Stack parent;
                Stack (Node node, Stack parent) {
                    this.node=node;
                    this.parent=parent;
                }
            }
            Stack stack = null;
            {
                put(root);
            }
            @Override
            public boolean hasNext() {
                return stack != null;
            }

            @Override
            public E next() {
                E res = stack.node.elem;
                Node right = stack.node.right;
                stack = stack.parent;
                put(right);
                return res;
            }
            void put (Node node) {
                if (node != null) {
                    stack = new Stack(node, stack);
                    put(node.left);
                }
            }
        };
    }

    @Override
    public void forEach (Consumer<? super E> consumer) {forEach(root, consumer);}
    private void forEach (Node node, Consumer<? super E> consumer) {
        if (node != null) {
            forEach(node.left, consumer);
            consumer.accept(node.elem);
            forEach(node.right, consumer);
        }
    }



    @Override
    public String toString() {
        AtomicReference<Boolean> firstTime= new AtomicReference<>(false);
        StringBuilder s = new StringBuilder();
        s.append('[');
        forEach(e -> {
            if (firstTime.get().booleanValue())
                s.append(", ");
            firstTime.set(true);
            s.append(e);
        });
        s.append(']');
        return s.toString();
    }
}


public interface Comparable <T> {
    int compareTo (T o);
}




public class Int implements Comparable<Int> {
    int x;
    Int (int x) {
        this.x=x;
    }
    @Override
    public int compareTo(Int o) {
        return x - o.x;
    }

    @Override
    public String toString() {
        return Integer.toString(x);
    }
}



import java.util.Iterator;
import java.util.function.Consumer;

public interface Iterable <E> {
    Iterator<E> iterator();
    void forEach(Consumer<? super E> consumer);
}



public interface Iterator <T> {
    boolean hasNext ();
    T next ();
}


public class Main {
    public static void main (String[] argv) {
        BST<Int> bst = new BST<>();
        int[] a = {4, 7, 9, 3, 1};
        for (int e : a)
            bst.add(new Int(e));
        System.out.println(bst);
        /*for (int i : bst) {

        }*/
    }
}