public Node busca(String obj) {
		Node current = firstNode;
		while (current != null) {
			if (current.getData().equals(obj)) {
				return current;
			}
			current = current.getNext();
		}
		return null;
	}

public BSTNode search(int el) {
		return search(root, el);
	}

	private BSTNode search(BSTNode p, int el) {
		while (p != null) {
			/* se valor procurado == chave do no retorna referencia ao no */
			if (el == p.key)
				return p;
			/*
			 * se valor procurado < chave do no, procurar na sub-arvore esquerda
			 * deste no
			 */
			else if (el < p.key)
				p = p.left;
			/*
			 * se valor procurado > chave do no, procurar na sub-arvore direita
			 * deste no
			 */
			else
				p = p.right;
		}
		// caso chave nao foi achada, retorna null
		return null;
	}

public BSTNode search(String nome) {
		return search(root, nome);
	}

	private BSTNode search(BSTNode p, String el) {
		while (p != null) {
			/* se valor procurado == chave do no retorna referencia ao no */
			if (el.equalsIgnoreCase(p.key.getNome()))
				return p;
			/*
			 * se valor procurado < chave do no, procurar na sub-arvore esquerda
			 * deste no
			 */
			else if (el.compareToIgnoreCase(p.key.getNome()) < 0)
				p = p.left;
			/*
			 * se valor procurado > chave do no, procurar na sub-arvore direita
			 * deste no
			 */
			else
				p = p.right;
		}
		// caso chave nao foi achada, retorna null
		return null;
	}

void searchsTree ( TreeNode* rNodePtr ) // void, porque ela não vai retornar nada, mas pensei em retornar um inteiro. Poderia cmeçar com int.

{

if ( rNodePtr == 0 ) // A árvore não está vazia

cout << “\n A Arvore esta vazia !!!\n”;

return;

int d; // crie uma variável
    int i = 0; // crie outra variável, para ser usada como contador
    
    else( rNodePtr == d ) // se raiz for igual ao nó 
    {

        return cout << "\n O elemento exite";
        

        else if ( rNodePtr < d ) se raiz for menor
        searchsTree ( rNodePtr -> getLeftPtr() ); // eu chamo a função que crie lá no inicío da função, antes da função main.
        i++;
        
        else if ( rNodePtr > d ) se raiz for menor
        searchsTree ( rNodePtr -> getRightPtr() );
        i++;
        }
        }

        O rNodePtr é a raiz, getLeftPtr, faz a raiz percorrer para o lado esquerdo e getRightPtr faz ela percorrer para o lado direito.

public void searchsTree ( TreeNode rNodePtr ) { // você precisa passar como parametro algo a ser pesquisado
// precisa retornar algo, ja que é uma busca, retornar o nó onde se encontra a informação é util

if ( rNodePtr == 0 ) // Este caso sera inutil, um nó nunca é 0, ele pode ser null, ou conter algo, então deveria ser feito rNodePtr.getData() == 0, por exemplo 
cout << "\n A Arvore esta vazia !!!\n"; // a variavel cout não aparece no método, ela não existe.
return; // aqui retornaria o teu nó por exemplo

}

public BSTNode search(String el) {
		return search(root, el);
	}

	private BSTNode search(BSTNode p, String el) {
		if (p == null || el.equalsIgnoreCase(p.key.getNome()))
			return p;
		else if (el.compareToIgnoreCase(p.key.getNome()) < 0)
			return search(p.left, el);
		else
			return search(p.right, el);
	}

public BSTNode search(int el) {
		return search(root, el);
	}

	private BSTNode search(BSTNode p, int el) {
		if (p == null || el == p.key.getNome())
			return p;
		else if (el  < p.key.getNome()))
			return search(p.left, el);
		else
			return search(p.right, el);
	}

public class BSTNode {
    protected int key;
    protected BSTNode left, right;
    
    public BSTNode() {
        left = right = null;
    }
    public BSTNode(int num) {
        this(num,null,null);
    }
    public BSTNode(int num, BSTNode lt, BSTNode rt) {
        this.key = num; left = lt; right = rt;
    }
	public int getKey() {
		return key;
	}
	public void setKey(int key) {
		this.key = key;
	}
	public BSTNode getLeft() {
		return left;
	}
	public void setLeft(BSTNode left) {
		this.left = left;
	}
	public BSTNode getRight() {
		return right;
	}
	public void setRight(BSTNode right) {
		this.right = right;
	}    
 
}

public class BST {
	private BSTNode root = null;

	public BST() {
	}

	public void clear() {
		root = null;
	}

	public boolean isEmpty() {
		return root == null;
	}

	public BSTNode getRootNode() {
		return root;
	}

	public boolean insert(int el) {
		BSTNode p = root, prev = null;
		// caso o valor ja exista na arvore, nao inserir e retornar false
		if (search(el) != null)
			return false;
		// procurando um lugar para colocar o novo noh
		while (p != null) {
			prev = p;
			if (el < p.key)
				p = p.left;
			else
				p = p.right;

		}
		// se arvore vazia
		if (root == null)
			root = new BSTNode(el);
		else if (prev.key < el)
			prev.right = new BSTNode(el);
		else
			prev.left = new BSTNode(el);
		return true;
	}

	
	public void insereArray(int[] array){
		for(int i = 0; i < array.length; i++){
			this.insert(array[i]);
		}
	}
	
	public int obtemMaior(){
		return retornaMaior(root, Integer.MIN_VALUE);
	}
	private int retornaMaior(BSTNode p, int num){
		
		if(p == null)
			return num;
		
		if(p != null){
			if(p.getKey() > num)
				num = p.getKey();
			else
				return num;
		}
		return retornaMaior(p.getRight(), num);
		
	}
	public int obtemMenor(){
		return retornaMenor(root, Integer.MAX_VALUE);
	}
	private int retornaMenor(BSTNode p, int num){
		
		if(p == null)
			return num;
		
		if(p != null){
			if(p.getKey() < num)
				num = p.getKey();
			else
				return num;
		}
		return retornaMenor(p.getLeft(), num);
		
	}
	
	public boolean isCheia(){
		int nivel = this.altura(root);
		int valor = (int) (Math.pow(2, nivel) - 1);
		
		if(contaNos() == valor)
			return true;
		else
			return false;
	}
	
	public BSTNode search(int el) {
		return search(root, el);
	}

	private BSTNode search(BSTNode p, int el) {
		while (p != null) {
			/* se valor procurado == chave do noh retorna referencia ao noh */
			if (el == p.key)
				return p;
			/*
			 * se valor procurado < chave do noh, procurar na sub-arvore esquerda
			 * deste noh
			 */
			else if (el < p.key)
				p = p.left;
			/*
			 * se valor procurado > chave do noh, procurar na sub-arvore direita
			 * deste noh
			 */
			else
				p = p.right;
		}
		// caso chave nao foi achada, retorna null
		return null;
	}

	public BSTNode searchR(int el) {
		return searchR(root, el);
	}

	private BSTNode searchR(BSTNode p, int el) {
		if (p == null || el == p.key)
			return p;
		else if (el < p.key)
			return searchR(p.left, el);
		else
			return searchR(p.right, el);
	}

	protected BSTNode searchFather(int el) {
		BSTNode p = root;
		BSTNode prev = null;
		while (p != null && !(p.key == el)) { // acha o noh p com a chave el
			prev = p;
			if (p.key < el)
				p = p.right;
			else
				p = p.left;
		}
		if (p != null && p.key == el)
			return prev;
		return null;
	}

	public void deleteByCopying(int el) {
		BSTNode node, father = null;
		node = search(el); // procura noh a ser deletado
		if (node != null && node.key == el) {
			if (node != root)
				father = searchFather(el); // procura pai do noh a ser deletado
			if (node.right == null) { // noh nao tem filho direito (caso 2);
				if (node == root)
					root = node.left;
				else if (father.left == node)
					father.left = node.left;
				else
					father.right = node.left;
			} else if (node.left == null) { // noh nao tem filho esquerdo (caso
				// 2)
				if (node == root)
					root = node.right;
				else if (father.left == node)
					father.left = node.right;
				else
					father.right = node.right;
			} else { // noh tem ambos os filhos: fazer remocao por copia
				BSTNode tmp = node.left; // 1. pegando sub-arvore esquerda
				while (tmp.right != null) { // 2. acha a posicao mais a direita
					tmp = tmp.right; // da sub-arvore esquerda do noh
				}
				deleteByCopying(tmp.key); // remove por copia o noh que possui
				// o maior valor
				// da sub-arvore esquerda do noh a ser deletado
				node.key = tmp.key; // copia o valor da chave do maior noh
				// da sub-arvore esquerda
			}
		} else if (root != null)
			System.out.println("el " + el + " is not in the tree");
		else
			System.out.println("the tree is empty");
	}

	public void deleteByMerging(int el) {
		BSTNode tmp, node, father = null;
		node = search(el); // procura noh a ser deletado
		if (node != null && node.key == el) {
			if (node != root)
				father = searchFather(el); // procura pai do noh a ser deletado
			if (node.right == null) { // noh nao tem filho direito (caso 2);
				if (root == node)
					root = node.left;
				else if (father.left == node)
					father.left = node.left;
				else
					father.right = node.left;
			} else if (node.left == null) { // noh nao tem filho esquerdo (caso
				// 2)
				if (root == node)
					root = node.right;
				else if (father.left == node)
					father.left = node.right;
				else
					father.right = node.right;
			} else { // se tem dois filhos, faz delecao por fusao
				tmp = node.left; // pega sub-arvore esquerda
				while (tmp.right != null)
					// pega filho mais a direita da sub-arvore esquerda
					tmp = tmp.right;
				tmp.right = node.right; // o filho mais a direita da sub-arvore
				// esquerda passa a ter
				// como filho direito o filho direito do noh a ser deletado
				if (root == node)
					root = node.left;
				else if (father.left == node)
					father.left = node.left;
				else
					father.right = node.left;
			}
		} else if (root != null)
			System.out.println("el " + el + " is not in the tree");
		else
			System.out.println("the tree is empty");
	}

	public int contaNos() {
		int cont = 0;
		cont = contaNos(root, cont);
		return cont;
	}

	private int contaNos(BSTNode p, int cont) {
		if (p != null) {
			cont++;
			cont = contaNos(p.left, cont);
			cont = contaNos(p.right, cont);
		}
		return cont;
	}
        
        public int qtFolha() {
		return contaFolha(root);
	}

	private int contaFolha(BSTNode p) {
		if (p == null)
			return 0;
		else if(p != null)
			if(p.getLeft() == null && p.getRight() == null)
				return 1;

			return contaFolha(p.left) + contaFolha(p.right);
	}
        
	public int altura() {
		return altura(root);
	}

	private int altura(BSTNode p) {
		if (p == null)
			return 0;
		return max(altura(p.left), altura(p.right)) + 1;
	}
        
        private int max(int i, int j) {
		return i > j ? i : j;
	}
        
        public void inorder() {
		inorder(root);
	}

	private void inorder(BSTNode p) {
		if (p != null) {
			inorder(p.left);
			System.out.print(p.key + " ");
			inorder(p.right);
		}
	}

	public void preorder() {
		preorder(root);
	}

	private void preorder(BSTNode p) {
		if (p != null) {
			System.out.print(p.key + " ");
			preorder(p.left);
			preorder(p.right);
		}
	}

	public void postorder() {
		postorder(root);
	}

	private void postorder(BSTNode p) {
		if (p != null) {
			postorder(p.left);
			postorder(p.right);
			System.out.print(p.key + " - ");
		}
	}

	protected void percursoEmLargura() throws OverflowException,
			UnderflowException {
		Queue q = new Queue(100);
		if (root != null)
			q.enqueue(root.key);
		int nivelAtual = 0;
		while (!q.isEmpty()) {
			int chave = q.dequeue();
			BSTNode n = search(chave);
			if (getNivel(n) > nivelAtual) {
				System.out.println();
				nivelAtual++;
				imprimeNroEspacos(getNroEspacos(getNivel(n), altura()) / 2);
			}
			System.out.print(imprimeChar(n.key));
			imprimeNroEspacos(getNroEspacos(getNivel(n), altura()));
			if (n.left != null)
				q.enqueue(n.left.key);
			if (n.right != null)
				q.enqueue(n.right.key);
		}
                System.out.println();
        }

        public int getNivel(BSTNode n) {
		return getNivel(root, n.key, 0);
	}

	protected int getNivel(BSTNode p, int chave, int h) {
		if (p == null)
			return -1;
		else if (p.key == chave)
			return h + 1;
		else if (chave < p.key)
			return getNivel(p.left, chave, h + 1);
		else
			return getNivel(p.right, chave, h + 1);
	}
	
	public int getDescendentes(int el){
		BSTNode p = this.search(el);
		return numDescendentes(p);
	}
	private int numDescendentes(BSTNode p){
		
		if(p != root)
		return this.contaNos(p, -1);
		
		else
			return -1;
	}

	public String imprimeChar(int n) {
		String s = "";
		if (n / 100 > 0)
			s = n + "";
		else if (n / 10 > 0)
			s = " " + n;
		else
			s = " " + n + " ";
		return s;

	}

	public int getNroEspacos(int nivel, int h) {
		int nro = (getNroNosNivel(h) * 2 - getNroNosNivel(nivel))
				/ getNroNosNivel(nivel);
		return nro;
	}

        public int getNroNosNivel(int nivel) {
		double n = Math.pow(2, nivel - 1);
		return (int) n;
	}

	public void imprimeNroEspacos(int n) {
		for (int i = 1; i <= n; i++)
			System.out.print("   ");
	}

	/* metodo de autoria de Leonardo Zandona - 2006/2 */
	public void displayTree() {
		if (isEmpty()) {
			System.out.println("Arvore vazia!");
			return;
		}
		String separator = String.valueOf("  |__");
		System.out.println(this.root.key);
		displaySubTree(root.left, separator);
		displaySubTree(root.right, separator);
	}

	private void displaySubTree(BSTNode node, String separator) {

		if (node != null) {

			BSTNode father = this.searchFather(node.key);
			if (node.equals(father.left) == true) {
				System.out.println(separator + node.key + " (ESQ)");
			} else {
				System.out.println(separator + node.key + " (DIR)");
			}

			displaySubTree(node.left, "     " + separator);
			displaySubTree(node.right, "     " + separator);
		}
	}
	
	public static void main(String args[]) {
		BST b = new BST();
		b.insert(5);
		b.insert(3);
		b.insert(7);
		b.insert(6);
		b.insert(10);
		b.insert(4);		
		b.insert(2);
		System.out.println(b.obtemMaior());
		System.out.println(b.obtemMenor());
		System.out.println(b.isCheia());
	}
}