Como dito na introdução, as rotinas de inserção e pesquisa são bastante simples. O algoritmo para inserir um novo elemento na árvore é o seguinte:

	Inserir(elemento) {
		Se (elemento <= raiz) Inserir (arvore esquerda)
		Senão Inserir (arquivo direita)
	}

Como a estrutura de uma árvore binária é recursiva, também construiremos funções recursivas, e como toda função recursiva, a função para inserir um elemento também precisa de uma condição de pausa. Uma boa condição de pausa é quando a raiz fornecida como argumento for NULL. Assim, além de uma condição de pausa, teremos também uma deixa para inserir o elemento.

Primeiro, as definições básicas da estrutura da árvore:

typedef struct folha* Folha;

struct folha {
	int	info;

	Folha	esquerda;
	Folha	direita;
};

Agora, a função para inserir um novo elemento na árvore (completa, depois comentada passo a passo):

/* @ Folha inserir (Folha raiz, int info)
 *
 * Argumentos
 * ----------
 *	raiz	ponteiro para 'struct folha', estrutura de dado básica para
 *		construção da árvore
 *	info	nova informação a ser inserida
 *
 * Retorno
 * -------
 *	NULL	em caso de erro
 *	Folha	em caso de sucesso (nó 'raiz')
 */
Folha inserir (Folha raiz, int info)
{
	if (!raiz) {
		/* significa que o ponteiro é nulo, e que está é a posição
		 * para inserção.
		 *
		 * 1. Alocar e checar memória
		 */
		if (!(raiz = FOLHA)) {
			perror("inserir:malloc()");
			return NULL;
		}

		/* 2. Cópia da Informação
		 * 3. Ponteiros de referência
		 * 4. Retorno da nova folha
		 */
		raiz->info = info;
		raiz->esquerda = raiz->direita = NULL;

		return raiz;
	} else if (info > raiz->info)
		raiz->direita = inserir (raiz->direita, info);
	else
		raiz->esquerda = inserir (raiz->esquerda, info);

	/* retorna o ponteiro raiz
	 *
	 * Isso é necessário pois a função inserir é recursiva, e seu retorno
	 * é sempre atribuido ao mesmo ponteiro passado como argumento 'raiz',
	 *
	 * raiz->esquerda = inserir(raiz->esquerda,info)
	 * raiz->direita  = inserir(raiz->direta,  info)
	 */
	return raiz;
}

Para utilizar a função, inserir:

	Folha arvore = NULL;

	arvore = inserir(arvore, 4);
	...
	// as chamadas subsequentes a inserir serão:
	inserir (arvore, 4);

Dissecando a função:

Folha inserir (Folha raiz, int info)

A linha acima é a declaração da função e seus argumentos. A função "inserir" é declarada como do tipo "Folha" - tipo definido no início do código como um ponteiro para o tipo "struct folha" (typedef struct folha *Folha).

A seguir, a lista de parâmetros define os dois argumentos necessários para chamarmos a função: raiz e info. raiz é do tipo "Folha" (ponteiro para "struct folha"), e info é do tipo "int" e é nosso dado a ser inserido. Na chamada original, "raiz" será a raiz principal da árvore - nas subsequentes será uma subárvore esquerda ou direita da raiz original.

	if (!raiz) {
		/* significa que o ponteiro é nulo, e que está é a posição
		 * para inserção.
		 *
		 * 1. Alocar e checar memória
		 */
		if (!(raiz = (Folha) malloc (sizeof(struct folha)))) {
			perror("inserir:malloc()");
			return NULL;
		}

		/* 2. Cópia da Informação
		 * 3. Ponteiros de referência
		 * 4. Retorno da nova folha
		 */
		raiz->info = info;
		raiz->esquerda = raiz->direita = NULL;

		return raiz;
	}

A primeira parte do escopo da função é um bloco "if". Esse bloco é nossa condição de parada da recursão. Assim que "raiz" for NULL, (!raiz) será avaliado como VERDADEIRO e nosso bloco será executado (Também funciona para detectar uma nova árvore). A primeira ação a ser tomada é alocar memória para o novo nó e verificar se a chamada a malloc() foi bem sucedida.

Quando nos asseguramos que a memória foi alocada corretamente, começamos as atribuições. "raiz->info = info" atribui ao campo info de raiz a informação "info" de nossa lista de argumentos. A próxima linha inicializa ambos os ponteiros de referência "esquerda" e "direita" como NULL (isso é importante, uma vez que se deixarmos lixo nos ponteiros, as rotinas de operação na árvore não funcionarão corretamente, já que são baseadas em um teste condicional de negação).

É importante notar que esse algoritmo não trabalha com reestruturação de nós, então, por definição, todos os novos nós inseridos na árvore são "folhas" de acordo com a definição formal (ambas as subárvores nulas). A seguir retornamos a nova raiz que criamos.

Agora passamos para a parte da recursão, e é onde o algoritmo de árvore é implementado:

	else if (info > raiz->info)
		raiz->direita = inserir (raiz->direita, info);
	else
		raiz->esquerda = inserir (raiz->esquerda, info);

	return raiz;

Começamos com um "else if" em nosso primeiro "if(!raiz)". Nessa linha testamos se o valor do parâmetro "info" é MAIOR QUE "info" da "raiz" atual - lembre-se que "raiz" foi passado como argumento para a função. Caso a condição seja avaliada como verdadeira, significa que "info" é maior que a informação contida na raiz atual, então ela deve ser inserida à direita da raiz. Para isso, utilizamos:

raiz->direita = inserir (raiz->direita, info);

O que estamos fazendo aqui é chamar a função inserir() e fornecendo à ela a mesma "info" que nos foi passada a primeiro momento. Entretanto, passamos um novo argumento como raiz: "raiz->direita". "raiz->direita" refere-se à subárvore direita da "raiz" atual (argumento da função).

Também atribuímos o retorno dessa função ao ponteiro "raiz->direita". Lembre-se que a função "inserir" vai retornar uma nova raiz caso o parâmetro "raiz" seja NULL, então, caso a "raiz->direita" seja NULL, nos será retornado um novo ponteiro que atribuiremos à "raiz->direita". Reserve um tempo para entender o que está acontecendo aqui.

A seguir, completamos as condições de inserção com um "else". Esta condicional representa todo o resto não tratado pelos "if" e "else if" acima. Ou seja, quando uma "info" é *menor ou igual* à "raiz->info", realizaremos uma chamada à "inserir" exatamente como a acima, exceto que dessa vez, usaremos "raiz->esquerda".

raiz->esquerda = inserir (raiz->esquerda, info);

Após a sequência condicional, retornamos a raiz. E fazemos isso para dar consistência às definições condicionais acima mencionadas. Pense um pouco em como é o processo de procura do local para inserir um nó. A função "inserir" entra em modo recursivo e sempre retorna a raiz que foi passada como argumento.

Para percorrer a árvore, chamamos a função "inserir" repetidamente com os ponteiros "esquerda" e "direita" de raiz e atribuímos o retorno da função à eles. Isso significa que a caso não retornemos a "raiz", iremos criar inconsistências na árvore (buracos!).