public class Node<T>{
    private T value;
    private int height;
    private Node<T> left;
    private Node<T> right;
    public Node(T value) {
        this.value = value;
        this.height = 1;
        this.left = null;
        this.right = null;
    }
    public T getValue() {
        return value;
    }
    public void setValue(T value) {
        this.value = value;
    }
    public int getHeight() {
        return height;
    }
    public void setHeight(int height) {
        this.height = height;
    }
    public Node<T> getLeft() {
        return left;
    }
    public void setLeft(Node<T> left) {
        this.left = left;
    }
    public Node<T> getRight() {
        return right;
    }
    public void setRight(Node<T> right) {
        this.right = right;
    }
    @Override
    public String toString() {
        // TODO Auto-generated method stub
        return this.value.toString();
    }
}

    public static <T> Node<T> insert(Node<T> root, T value){
        Node<T> node = new Node<T>(value);
        if(root == null) {
            return node;
        }
        int temp = 0;
        Node<T> prev = root;
        while(prev!=null) {
            temp = ((Comparable)prev.getValue()).compareTo(value);
            if(temp == 0) {
                return root;
            }else if(temp == 1) {
                if(prev.getLeft()==null) {
                    prev.setLeft(node);
                }
                prev = prev.getLeft();
            }else {
                if(prev.getRight()==null) {
                    prev.setRight(node);
                }
                prev = prev.getRight();
            }
        }
        return root;
    }