ArvoreBinaria.java

public class ArvoreBinaria {

  public No raiz;
	
	public No insere(int chave) {
		
		if (raiz == null) {
			raiz = new No();
			raiz.chave = chave;
			return raiz;
		} 

		No atual = raiz;
		
		return inserir(chave, atual);
	}

	private No inserir(int chave, No atual) {
		if  (chave < atual.chave) {
			if (atual.esquerda == null) {
				No filho = new No();
				filho.chave = chave;
				filho.pai = atual;
				atual.esquerda = filho;
				return filho;
			} else {
				return inserir(chave, atual.esquerda);
			}
		} else if (chave > atual.chave) {
			if (atual.direita == null) {
				No filho = new No();
				filho.chave = chave;
				filho.pai = atual;
				atual.direita = filho;
				return filho;
			} else {
				return inserir(chave, atual.direita);				
			}
		}
		
		return null;
	}
	
	public int busca(int chave) {
		return 0;
	}
}

class No {
	public int chave;
	public No pai;
	public No direita;
	public No esquerda;
}

ArvoreBinariaTest.java

import static org.junit.Assert.*;
import junit.framework.Assert;

import org.junit.Test;


public class ArvoreBinariaTest {

  @Test
	public void cenario1() {
		ArvoreBinaria arvore = new ArvoreBinaria();
		
		No no5 = arvore.insere(5);
		No no8 = arvore.insere(8);
		No no3 = arvore.insere(3);
		No no2 = arvore.insere(2);
		No no4 = arvore.insere(4);
		No no6 = arvore.insere(6);
		No no7 = arvore.insere(7);
		No no1 = arvore.insere(1);
		No no9 = arvore.insere(9);

		Assert.assertNull(no5.pai);
		Assert.assertEquals(no5.esquerda, no3);
		Assert.assertEquals(no3.pai, no5);
		Assert.assertEquals(no5.direita, no8);
		Assert.assertEquals(no8.pai, no5);
	}
}