Arvore Binaria

public class ArvoreBinariaNovo {

    private static class Node {

        public Node noEsquerda, noDireita;
        public int valor;

        public Node(int valor) {
            this.valor = valor;
            this.noEsquerda = null;
            this.noDireita = null;
        }

        @Override
        public String toString() {
            return "" + this.valor;
        }
    }

    private Node raiz;

    public ArvoreBinariaNovo() {
        raiz = null;
    }

    public void inserir(int valor) {
        inserir(raiz, valor);
    }

    private void inserir(Node node, int valor) {
        if (node.valor == valor)
            return;

        if (valor < node.valor) {
            if(node.noEsquerda != null) {
                insert(node.noEsquerda, valor);
            } else {
                node.noEsquerda = new Node(valor);
            }
        } else if (valor > node.valor) {
            if(node.noDireita != null) {
                insert(node.noDireita, valor);
            } else {
                node.noDireita = new Node(valor);
            }
        }
    }

    public boolean existe(int valor) {
        return existe(raiz, valor);
    }

    private boolean existe(Node node, int valor) {
        if (node == null) {
            return false;
        }

        if (valor == node.valor) {
            return true;
        }

        if (valor < node.valor) {
            return existe(node.noEsquerda, valor);
        } else {
            return existe(node.noDireita, valor);
        }
    }

    public boolean remove(int valor) {
        if (!existe(valor)) {
            return false;
        } else {
            remove(raiz, valor);
            return true;
        }
    }

    private int elemMin(Node node) {
        int min = node.valor;

        while (node.noEsquerda != null) {
            min = node.noEsquerda.valor;
            node = node.noEsquerda;
        }
        return min;
    }

    private Node remove(Node node, int valor) {
        if (node == null) {
            return node;
        }

        if (valor < node.valor) {
            node.noEsquerda = remove(node.noEsquerda, valor);
        } else if (valor > node.valor) {
            node.noDireita = remove(node.noDireita, valor);
        } else {
            if (node.noEsquerda == null) {
                return node.noDireita;
            } else if (node.noDireita == null) {
                return node.noEsquerda;
            }

            node.valor = elemMin(node.noDireita);
            node.noDireita = remove(node.noDireita, node.valor);
        }
        return node;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        appendToString(raiz, sb);

        return sb.toString();
    }

    private void appendToString(Node node, StringBuilder sb) {
        if (node == null) {
            return;
        }

        sb.append("(" + node + ", " + node.noEsquerda + ", " + node.noDireita + ")\n");
        appendToString(node.noEsquerda, sb);
        appendToString(node.noDireita, sb);
    }

    public static void main(String[] args) {
        ArvoreBinariaNovo arv = new ArvoreBinariaNovo();

        arv.inserir(50);
        arv.inserir(30);
        arv.inserir(20);
        arv.inserir(18);
        arv.inserir(16);
        arv.inserir(19);
        arv.inserir(22);
        arv.inserir(40);
        arv.inserir(35);
        arv.inserir(42);
        arv.inserir(70);
        arv.inserir(60);
        arv.inserir(80);
        arv.inserir(75);

        System.out.println(arv);

        //remover raiz
        System.out.println(arv.remove(50));

        //remover dois filhos
        //System.out.println(arv.remove(20));

        //remover um filho
        //System.out.println(arv.remove(80));

        //remover sem filhos
        //System.out.println(arv.remove(16));

        System.out.println(arv);
    }
}