Navegando em Hierarquias: Árvores

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;     // O valor do nó
    this.left = left;   // Referência para o filho da esquerda (outro TreeNode)
    this.right = right; // Referência para o filho da direita (outro TreeNode)
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null; // A BST começa vazia
  }

  insert(val) {
    const newNode = new TreeNode(val);
    if (!this.root) {
      this.root = newNode;
      return this;
    }

    let current = this.root;
    while (true) {
      if (val === current.val) return undefined; // Não permite valores duplicados
      if (val < current.val) {
        if (current.left === null) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } else {
        if (current.right === null) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
  }

  search(val) {
    if (!this.root) return false;

    let current = this.root;
    while (current) {
      if (val === current.val) return true; // Encontrou!
      if (val < current.val) {
        current = current.left;
      } else {
        current = current.right;
      }
    }

    return false; // Não encontrou
  }
}

// --- DFS: Depth-First Search ---

// 1. In-Order (Esquerda, Raiz, Direita) -> Para BSTs, resulta em ordem crescente.
function inOrder(node) {
  if (!node) return;
  inOrder(node.left);
  console.log(node.val);
  inOrder(node.right);
}

// 2. Pre-Order (Raiz, Esquerda, Direita) -> Útil para copiar a árvore.
function preOrder(node) {
  if (!node) return;
  console.log(node.val);
  preOrder(node.left);
  preOrder(node.right);
}

// 3. Post-Order (Esquerda, Direita, Raiz) -> Útil para deletar nós.
function postOrder(node) {
  if (!node) return;
  postOrder(node.left);
  postOrder(node.right);
  console.log(node.val);
}

// --- BFS: Breadth-First Search ---

// 4. Level-Order -> Visita a árvore nível por nível, usando uma Fila.
function levelOrder(root) {
  if (!root) return;

  const queue = [root]; // Usa uma fila para controlar os nós a visitar

  while (queue.length > 0) {
    const node = queue.shift(); // Pega o primeiro da fila
    console.log(node.val);

    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
}

class TrieNode {
  constructor() {
    this.children = {};    // Mapeia caracteres para outros TrieNodes
    this.isEndOfWord = false; // Flag para marcar o fim de uma palavra
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  // Insere uma palavra na Trie
  insert(word) {
    let current = this.root;
    for (const char of word) {
      if (!current.children[char]) {
        current.children[char] = new TrieNode();
      }
      current = current.children[char];
    }
    current.isEndOfWord = true;
  }

  // Procura por uma palavra completa na Trie
  search(word) {
    let current = this.root;
    for (const char of word) {
      if (!current.children[char]) {
        return false; // Caminho não existe
      }
      current = current.children[char];
    }
    return current.isEndOfWord; // Retorna true apenas se for uma palavra completa
  }

  // Verifica se existe alguma palavra com um dado prefixo
  startsWith(prefix) {
    let current = this.root;
    for (const char of prefix) {
      if (!current.children[char]) {
        return false;
      }
      current = current.children[char];
    }
    return true;
  }
}

function rightRotate(y) {
  const x = y.left;
  const B = x.right;

  // Realiza a rotação
  x.right = y;
  y.left = B;

  // Retorna a nova raiz da sub-árvore
  return x;
}

function leftRotate(x) {
  const y = x.right;
  const B = y.left;

  // Realiza a rotação
  y.left = x;
  x.right = B;

  // Retorna a nova raiz da sub-árvore
  return y;
}