Escreva uma função não-recursiva que verifique a existência de um valor X na árvore binária.

Passo 1

A questão pede para escrever uma função não-recursiva que verifique se um valor X está presente em uma árvore binária. O conteúdo envolvido é travessia (search) em uma árvore binária usando estruturas de dados auxiliares (pilha ou fila). Para resolver, vamos precisar entender como usar uma pilha para simular a chamada recursiva de uma busca em profundidade (DFS).

Passo 2

A estratégia escolhida é realizar uma busca em profundidade (DFS) iterativa, usando uma pilha. Em cada iteração, retiramos o nó do topo da pilha, comparamos seu valor com X e, se não for igual, empilhamos seus filhos (primeiro filho esquerdo, depois filho direito, ou vice-versa, conforme preferência).
Inicializamos uma pilha vazia e, se a raiz não for nula, empilhamos a raiz. Em seguida, entramos em um laço que continua enquanto a pilha não estiver vazia.

Passo 3

Dentro do laço, retiramos o nó do topo da pilha. Se o valor desse nó for igual a X, retornamos verdadeiro. Caso contrário, se o nó tiver filho direito, empilhamos esse filho; depois, se tiver filho esquerdo, empilhamos o filho esquerdo. Isso garante que o próximo nó a ser processado seja o filho esquerdo (comportamento clássico de DFS).
Se o laço terminar sem encontrar X, retornamos falso, indicando que o valor não está presente na árvore.

Resposta

// Definição simplificada de nó de árvore binária
struct TreeNode {
int valor;
TreeNode *esq;
TreeNode *dir;
};
bool existeValor(TreeNode *raiz, int X) {
if (raiz == nullptr) {
return false;
}
// Pilha para nós a visitar
std::stack<TreeNode*> pilha;
pilha.push(raiz);

while (!pilha.empty()) {
    TreeNode *no = pilha.top();
    pilha.pop();

    // Verifica se o valor do nó é X
    if (no->valor == X) {
        return true;
    }

    // Empilha primeiro o filho direito (vai ser processado depois)
    if (no->dir != nullptr) {
        pilha.push(no->dir);
    }
    // Empilha o filho esquerdo (será processado em seguida)
    if (no->esq != nullptr) {
        pilha.push(no->esq);
    }
}

// Se percorrer toda a árvore sem encontrar X
return false;
}

Exercícios relacionados