Inversão de árvore binária com JavaScript

// Definição da estrutura do nó da árvore binária
class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// Função para inverter a árvore binária (recursiva)
function invertTree(root) {
    // Caso base: se o nó é null, retorna null
    if (root === null) {
        return null;
    }
    
    // Salva temporariamente o filho esquerdo
    const temp = root.left;
    
    // Troca os filhos
    root.left = root.right;
    root.right = temp;
    
    // Recursivamente inverte as subárvores
    invertTree(root.left);
    invertTree(root.right);
    
    return root;
}

// Versão iterativa usando pilha
function invertTreeIterative(root) {
    if (root === null) {
        return null;
    }
    
    const stack = [root];
    
    while (stack.length > 0) {
        const node = stack.pop();
        
        // Troca os filhos
        const temp = node.left;
        node.left = node.right;
        node.right = temp;
        
        // Adiciona os filhos não-nulos à pilha
        if (node.left) stack.push(node.left);
        if (node.right) stack.push(node.right);
    }
    
    return root;
}

// Função auxiliar para imprimir a árvore (in-order traversal)
function printInOrder(root) {
    if (root === null) return [];
    
    const result = [];
    const stack = [];
    let current = root;
    
    while (current !== null || stack.length > 0) {
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        result.push(current.val);
        current = current.right;
    }
    
    return result;
}

// Exemplo de uso
console.log("=== Exemplo de Inversão de Árvore Binária ===");

// Criando a árvore original:
//       4
//      / \
//     2   7
//    / \ / \
//   1  3 6  9
const root = new TreeNode(4);
root.left = new TreeNode(2);
root.right = new TreeNode(7);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(9);

console.log("Árvore original (in-order):", printInOrder(root));

// Invertendo a árvore
const invertedRoot = invertTree(root);

console.log("Árvore invertida (in-order):", printInOrder(invertedRoot));

// A árvore invertida ficará assim:
//       4
//      / \
//     7   2
//    / \ / \
//   9  6 3  1