Invert Binary Tree — Entendendo Árvores Binárias na Prática

Um dos problemas mais conhecidos para quem está estudando estruturas de dados e algoritmos é o Invert Binary Tree, também conhecido como inversão de uma árvore binária.

Esse problema ficou especialmente famoso por aparecer em entrevistas técnicas e por ser um excelente exercício para entender:

Árvores binárias
Recursão
Estruturas de dados
Travessia de árvores
Pensamento algorítmico

Mas antes de resolver o problema, precisamos entender:

O que exatamente é uma árvore binária?

1. O que é uma árvore binária?

Uma árvore binária é uma estrutura de dados formada por nós (nodes).

Cada nó pode possuir, no máximo:

2 filhos

Esses filhos são chamados de:

Left  → Filho da esquerda

Right → Filho da direita

Por exemplo:

Nesse exemplo:

é a raiz (root) da árvore.

O nó 4 possui dois filhos:

2 → esquerda

7 → direita

O nó 2 também possui dois filhos:

1 → esquerda

3 → direita

E assim por diante.

2. Por que é chamada de "árvore"?

O nome vem da forma como a estrutura é organizada.

Temos:

        ROOT
         │
         ▼
       PARENT
       /    \
      ▼      ▼
    CHILD  CHILD

Diferente de uma árvore do mundo real, ela normalmente é desenhada com a raiz no topo e os filhos abaixo.

Por exemplo:

             10
           /    \
          5      20
         / \    /  \
        2   7  15  30

A estrutura começa em um único ponto:

E vai se ramificando.

Por isso o nome:

Tree (árvore)

3. O que é um Node?

Cada elemento da árvore é um Node.

Um Node de uma árvore binária normalmente possui:

value
left
right

Em TypeScript, podemos representar assim:

class TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(
    value: number,
    left: TreeNode | null = null,
    right: TreeNode | null = null
  ) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

Podemos criar uma árvore:

const root = new TreeNode(
  4,
  new TreeNode(
    2,
    new TreeNode(1),
    new TreeNode(3)
  ),
  new TreeNode(
    7,
    new TreeNode(6),
    new TreeNode(9)
  )
);

Que representa:

4. O problema do LeetCode

O problema Invert Binary Tree pede para inverter uma árvore binária.

Dada a árvore:

Precisamos obter:

Perceba o que aconteceu.

Em cada nó:

left

right

foram trocados.

Antes:

Node
├── Left
└── Right

Depois:

Node
├── Right
└── Left

5. A ideia da solução

A solução é surpreendentemente simples.

Para cada nó:

1. Trocar left e right
2. Fazer o mesmo no filho esquerdo
3. Fazer o mesmo no filho direito

Por exemplo:

        4
       / \
      2   7

Trocamos:

        4
       / \
      7   2

Agora precisamos fazer a mesma coisa em:

Esse processo continua até chegarmos aos nós que não possuem filhos.

6. A solução recursiva

Em TypeScript:

function invertTree(root: TreeNode | null): TreeNode | null {
  if (root === null) {
    return null;
  }

  const temp = root.left;

  root.left = root.right;
  root.right = temp;

  invertTree(root.left);
  invertTree(root.right);

  return root;
}

A lógica principal é:

const temp = root.left;

root.left = root.right;
root.right = temp;

Estamos simplesmente trocando os dois filhos.

Depois:

invertTree(root.left);
invertTree(root.right);

Aplicamos a mesma lógica para os filhos.

7. Entendendo a recursão

Imagine esta árvore:

        4
       / \
      2   7

Chamamos:

invertTree(root);

O root é:

Trocamos:

2 ↔ 7

Resultado:

        4
       / \
      7   2

Agora chamamos:

invertTree(7);

Depois:

invertTree(2);

Se o nó não possui filhos:

A função simplesmente termina.

O processo acontece para todos os nós da árvore.

8. Visualizando passo a passo

Árvore original:

Primeiro:

Depois, invertendo os filhos de 7:

Depois, invertendo os filhos de 2:

Resultado final:

9. Complexidade

Se a árvore possui n nós:

Time Complexity: O(n)

Precisamos visitar cada nó uma vez.

Em relação à memória:

Space Complexity: O(h)

Onde h é a altura da árvore.

Isso acontece porque utilizamos a pilha de chamadas da recursão.

Em uma árvore balanceada:

O(log n)

Em uma árvore completamente desbalanceada:

O(n)

Por exemplo:

Nesse caso, a árvore se comporta praticamente como uma lista.

10. Existe uma solução iterativa?

Sim.

Podemos utilizar uma fila:

function invertTree(root: TreeNode | null): TreeNode | null {
  if (root === null) {
    return null;
  }

  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const node = queue.shift()!;

    // Troca os filhos
    [node.left, node.right] = [node.right, node.left];

    if (node.left !== null) {
      queue.push(node.left);
    }

    if (node.right !== null) {
      queue.push(node.right);
    }
  }

  return root;
}

Essa abordagem utiliza uma travessia conhecida como:

Breadth-First Search (BFS)

A árvore é percorrida por níveis:

        4        ← Nível 1
       / \
      2   7      ← Nível 2
     / \ / \
    1  3 6  9    ← Nível 3

11. Mas onde isso é usado na vida real?

O problema do LeetCode é principalmente um exercício de algoritmos.

Na prática, provavelmente você não vai receber uma tarefa dizendo:

"Inverta essa árvore binária."

Porém, o conceito de percorrer e modificar estruturas de árvores aparece em diversos sistemas reais.

Um exemplo interessante é uma árvore de componentes de uma interface gráfica.

Imagine uma aplicação que possui:

Aplicação
   │
   ├── Header
   │
   ├── Main
   │    ├── Sidebar
   │    └── Content
   │
   └── Footer

Essa estrutura pode ser representada como uma árvore:

             App
          /   |   \
         /    |    \
     Header  Main  Footer
              / \
             /   \
        Sidebar Content

Frameworks e bibliotecas de UI trabalham constantemente com estruturas hierárquicas desse tipo.

12. Um exemplo prático: inverter uma árvore de componentes

Imagine que temos um menu lateral:

Menu
├── Home
├── Produtos
│   ├── Notebooks
│   └── Celulares
└── Contato

Agora imagine uma aplicação que precisa mudar a estrutura de navegação de uma interface para uma versão espelhada.

Por exemplo, em uma aplicação que suporta idiomas RTL:

Right-to-Left

Como:

Árabe
Hebraico

A interface pode precisar inverter a posição de determinados elementos.

Uma estrutura:

Sidebar
    │
    ├── Menu
    │
    └── Content

Pode se tornar:

Content
    │
    └── Menu

Embora aplicações reais normalmente utilizem técnicas específicas de CSS e layout para isso, o conceito por trás é semelhante:

Percorrer uma estrutura hierárquica e modificar a relação entre seus elementos.

13. Outro exemplo: árvore de pastas

Um exemplo ainda mais fácil de visualizar é um sistema de arquivos.

Imagine:

Projeto
├── src
│   ├── components
│   └── services
├── tests
└── package.json

Isso também é uma árvore.

Podemos representar:

type FileNode = {
  name: string;
  children: FileNode[];
};

Agora podemos percorrer a estrutura recursivamente:

function printTree(node: FileNode, level = 0) {
  console.log(" ".repeat(level * 2) + node.name);

  for (const child of node.children) {
    printTree(child, level + 1);
  }
}

Isso permite:

Projeto
  src
    components
    services
  tests
  package.json

Esse tipo de algoritmo é utilizado em:

Exploradores de arquivos
IDEs
Sistemas de gerenciamento de documentos
Menus hierárquicos
Categorias
Sistemas de permissões

14. E se quiséssemos inverter uma árvore de pastas?

Imagine:

Projeto
├── src
│   ├── components
│   └── services
└── tests

Em uma árvore binária, cada nó possui:

left
right

Então podemos inverter:

Projeto
├── tests
└── src
    ├── services
    └── components

Uma implementação seria:

function invertTree(node: FileNode): FileNode {
  if (node.children.length === 0) {
    return node;
  }

  node.children.reverse();

  for (const child of node.children) {
    invertTree(child);
  }

  return node;
}

Aqui temos a mesma ideia do problema do LeetCode:

1. Modificar o nó atual
2. Percorrer os filhos
3. Repetir recursivamente

A diferença é que uma árvore de arquivos pode ter vários filhos, enquanto uma árvore binária possui no máximo dois.

15. O verdadeiro aprendizado do problema

O objetivo do problema Invert Binary Tree não é necessariamente aprender a inverter árvores.

O principal aprendizado é entender como trabalhar com estruturas recursivas.

A ideia é:

Resolver o problema atual
        │
        ▼
Delegar o mesmo problema
para os filhos
        │
        ▼
Repetir até chegar
ao caso base

No caso da árvore:

              ROOT
             /    \
            /      \
         LEFT      RIGHT
          /          \
       LEFT         RIGHT

A mesma lógica é aplicada em cada nível.

Esse padrão aparece em vários problemas:

Árvores binárias
Árvores de arquivos
DOM
Menus
Estruturas de categorias
ASTs de compiladores
Estruturas de diretórios
Sistemas hierárquicos

Conclusão

Uma árvore binária é uma estrutura de dados em que cada nó possui, no máximo, dois filhos:

        Node
       /    \
    Left   Right

O problema Invert Binary Tree consiste em trocar esses dois filhos em todos os nós:

Antes:

        4
       / \
      2   7


Depois:

        4
       / \
      7   2

A solução mais comum utiliza recursão:

function invertTree(root: TreeNode | null): TreeNode | null {
  if (root === null) {
    return null;
  }

  [root.left, root.right] = [root.right, root.left];

  invertTree(root.left);
  invertTree(root.right);

  return root;
}

A grande lição é que recursão combina naturalmente com estruturas hierárquicas.

Quando encontramos uma estrutura que possui:

Pai
 ├── Filho
 │    ├── Neto
 │    └── Neto
 └── Filho

podemos frequentemente resolver o problema seguindo uma estratégia simples:

Resolva o nó atual e aplique a mesma lógica recursivamente aos seus filhos.

É exatamente esse padrão de pensamento que torna problemas como o Invert Binary Tree tão importantes em entrevistas e no estudo de estruturas de dados.

Invert Binary Tree

Invert Binary Tree — Entendendo Árvores Binárias na Prática

1. O que é uma árvore binária?

2. Por que é chamada de "árvore"?

3. O que é um Node?

4. O problema do LeetCode

5. A ideia da solução

6. A solução recursiva

7. Entendendo a recursão

8. Visualizando passo a passo

9. Complexidade

10. Existe uma solução iterativa?

11. Mas onde isso é usado na vida real?

12. Um exemplo prático: inverter uma árvore de componentes

13. Outro exemplo: árvore de pastas

14. E se quiséssemos inverter uma árvore de pastas?

15. O verdadeiro aprendizado do problema

Conclusão

Comments