Pré-ordem

Para implementar a travessia em pré-ordem de uma árvore binária sem recursão, utiliza-se uma pilha. Como a pré-ordem processa primeiro o nó raiz e depois as subárvores esquerda e direita, o nó raiz é emiplhado antes do loop principal. Durante a iteração, o nó superior é removido da pilha, seu valor é armazenado na lista de resutlados, e os nós filhos, se existentes, são empilhados. Para assegurar que a subárvore esquerda seja visitada primeiro, os nós da subárvore direita e esquerda são empilhados em sequência inversa: primeiro a direita, depois a esquerda, aproveitando a propriedade LIFO da pilha para ordenar o processamento corretamente.

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Stack<TreeNode> nodeStack = new Stack<>();
    nodeStack.push(root);
    while (!nodeStack.isEmpty()) {
        TreeNode current = nodeStack.pop();
        result.add(current.val);
        if (current.right != null) {
            nodeStack.push(current.right);
        }
        if (current.left != null) {
            nodeStack.push(current.left);
        }
    }
    return result;
}

Pós-ordem

A travessia em pós-ordem pode ser derivada da técnica em pré-ordem com ajustes. A pós-ordem segue a sequência esquerda-direita-raiz. Ao modificar a ordem de empilhamento das subárvores na travessia em pré-ordem (empilhando primeiro a esquerda, depois a direita), produz-se uma sequência raiz-direita-esquerda. Após obter essa lista, aplica-se uma inversão para alcançar a ordem desejada: esquerda-direita-raiz.

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Stack<TreeNode> nodeStack = new Stack<>();
    nodeStack.push(root);
    while (!nodeStack.isEmpty()) {
        TreeNode current = nodeStack.pop();
        result.add(current.val);
        if (current.left != null) {
            nodeStack.push(current.left);
        }
        if (current.right != null) {
            nodeStack.push(current.right);
        }
    }
    Collections.reverse(result);
    return result;
}

Em-ordem

A travessia em em-ordem adota uma abordagem distinta, seguindo a ordem esquerda-raiz-direita. Inicia-se pelo nó raiz, mas como o processamento deve ocorrer na subárvore esquerda primeiro, o nó atual é epmilhado e o percurso avança para a esquerda. Ao atingir um nó nulo, o último nó empilhado é removido da pilha, seu valor é adicionado à lista de resultados, e o percurso continua para a direita. O laço persiste enquanto houver elementos na pilha ou um nó atual válido.

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> nodeStack = new Stack<>();
    TreeNode current = root;
    while (current != null || !nodeStack.isEmpty()) {
        while (current != null) {
            nodeStack.push(current);
            current = current.left;
        }
        current = nodeStack.pop();
        result.add(current.val);
        current = current.right;
    }
    return result;
}