Como encontrar o pai de um elemento numa Árvore Binária?

Depende da implementação.

o que normalmente se faz é criar um objeto No que tem dois atributos, o nó direito e o nó esquerdo. logo o nó não sabe quem é o seu pai.

como fazer então? é simples. quando vc estiver procurando o No, guarde quem é o No pai

public No procura(No raiz, int valor) {
   //  na primeira vez quem é o nó pai? null
   No pai = null;
   return procura(pai, raiz, valor);
}
public No procura(No pai, No raiz, int valor) {
   if ( raiz == null ) { return null; }
   else if ( raiz.valor == valor ){ return pai; }
   // aqui vc decide como vai procurar, se vai fazer busca em largura ou profundidade.
}

Entendi o código e agradeço pela ajuda, porém o que preciso fazer é basicamente o seguinte:

• Passo somente a raiz como parâmetro para o método;
• A partir de então, preciso printar os pais (e armazená-los em um atributo pai) e seus respectivos filhos.

Não posso passar a variável valor como parâmetro, apenas a raiz.

implementa ai então