Деревья (Trees)

tags: dsa trees bst leetcode patterns

---

BST (Binary Search Tree)

Инвариант BST

• Для каждого узла: left.val < node.val < right.val (классический вариант без дублей)
• Позволяет отсекать половину дерева при поиске → O(h) для search/insert/delete
• h = высота: O(log n) для сбалансированного, O(n) в худшем случае (вырожденное в список)

Ключевая особенность: inorder → sorted

Inorder обход BST даёт значения в отсортированном порядке — это главное свойство для большинства задач

Типовые паттерны для BST

1. Prev в inorder (минимальная разница, валидация)

Когда: нужно сравнивать соседние по величине значения

var getMinimumDifference = function(root) {
  let prev = null;
  let ans = Infinity;
 
  function inorder(node) {
    if (!node) return;
    inorder(node.left);
 
    if (prev !== null) {
      ans = Math.min(ans, node.val - prev);
    }
    prev = node.val;
 
    inorder(node.right);
  }
 
  inorder(root);
  return ans;
};

• 🟢 530. Minimum Absolute Difference in BST
• 🟡 98. Validate Binary Search Tree

2. K-th smallest/largest

Когда: нужен элемент на позиции k в отсортированном порядке

var kthSmallest = function(root, k) {
  let count = 0;
  let result = null;
 
  function inorder(node) {
    if (!node || result !== null) return;
 
    inorder(node.left);
 
    count++;
    if (count === k) {
      result = node.val;
      return;
    }
 
    inorder(node.right);
  }
 
  inorder(root);
  return result;
};

• 🟡 230. Kth Smallest Element in a BST

3. Two Sum в BST

Вариант A: DFS + HashSet

var findTarget = function(root, k) {
  const seen = new Set();
 
  function dfs(node) {
    if (!node) return false;
 
    if (seen.has(k - node.val)) return true;
    seen.add(node.val);
 
    return dfs(node.left) || dfs(node.right);
  }
 
  return dfs(root);
};

Вариант B: Inorder + два указателя (экономит память)

var findTarget = function(root, k) {
  const sorted = [];
 
  function inorder(node) {
    if (!node) return;
    inorder(node.left);
    sorted.push(node.val);
    inorder(node.right);
  }
 
  inorder(root);
 
  let l = 0, r = sorted.length - 1;
  while (l < r) {
    const sum = sorted[l] + sorted[r];
    if (sum === k) return true;
    if (sum < k) l++;
    else r--;
  }
  return false;
};

• 🟢 653. Two Sum IV - Input is a BST
• 🟡 1214. Two Sum BSTs (Premium)

4. Search/Insert

Search: используй свойство BST для отсечения половины

var searchBST = function(root, val) {
  if (!root || root.val === val) return root;
  return val < root.val 
    ? searchBST(root.left, val) 
    : searchBST(root.right, val);
};

Insert:

var insertIntoBST = function(root, val) {
  if (!root) return new TreeNode(val);
 
  if (val < root.val) {
    root.left = insertIntoBST(root.left, val);
  } else {
    root.right = insertIntoBST(root.right, val);
  }
 
  return root;
};

• 🟢 700. Search in a Binary Search Tree
• 🟡 701. Insert into a Binary Search Tree

5. Delete Node

Когда: удаление узла с сохранением свойств BST (3 случая: лист, 1 ребенок, 2 ребенка)

var deleteNode = function(root, key) {
  if (!root) return null;
 
  if (key < root.val) {
    root.left = deleteNode(root.left, key);
  } else if (key > root.val) {
    root.right = deleteNode(root.right, key);
  } else {
    // Узел найден
    if (!root.left) return root.right;
    if (!root.right) return root.left;
 
    // 2 ребенка: ищем successor (min в правом поддереве)
    let minNode = root.right;
    while (minNode.left) minNode = minNode.left;
 
    root.val = minNode.val;
    root.right = deleteNode(root.right, minNode.val);
  }
  return root;
};

• 🟡 450. Delete Node in a BST

6. Range Sum Query

Когда: нужна сумма значений в диапазоне [low, high]

var rangeSumBST = function(root, low, high) {
  if (!root) return 0;
 
  // Отсекаем ветки вне диапазона
  if (root.val < low) return rangeSumBST(root.right, low, high);
  if (root.val > high) return rangeSumBST(root.left, low, high);
 
  // Узел в диапазоне — идём в обе стороны
  return root.val 
    + rangeSumBST(root.left, low, high) 
    + rangeSumBST(root.right, low, high);
};

• 🟢 938. Range Sum of BST

7. Балансировка BST

Когда: нужно перестроить дерево для оптимальной высоты

var balanceBST = function(root) {
  const arr = [];
  // 1. Inorder -> Sorted Array
  function inorder(node) {
    if (!node) return;
    inorder(node.left);
    arr.push(node.val);
    inorder(node.right);
  }
 
  // 2. Sorted Array -> Balanced BST
  function build(l, r) {
    if (l > r) return null;
    const mid = l + Math.floor((r - l) / 2);
    const node = new TreeNode(arr[mid]);
    node.left = build(l, mid - 1);
    node.right = build(mid + 1, r);
    return node;
  }
 
  inorder(root);
  return build(0, arr.length - 1);
};

• 🟡 1382. Balance a Binary Search Tree
• 🟢 108. Convert Sorted Array to Binary Search Tree

---

Binary Tree (общие деревья)

Обходы (traversals)

DFS — три порядка

// Preorder (NLR): node → left → right
function preorder(node) {
  if (!node) return;
  visit(node);
  preorder(node.left);
  preorder(node.right);
}
 
// Inorder (LNR): left → node → right
function inorder(node) {
  if (!node) return;
  inorder(node.left);
  visit(node);
  inorder(node.right);
}
 
// Postorder (LRN): left → right → node
function postorder(node) {
  if (!node) return;
  postorder(node.left);
  postorder(node.right);
  visit(node);
}

• 🟢 144. Binary Tree Preorder Traversal
• 🟢 94. Binary Tree Inorder Traversal
• 🟢 145. Binary Tree Postorder Traversal

BFS (level-order)

Стандартный шаблон (без shift для производительности):

function levelOrder(root) {
  if (!root) return [];
 
  const result = [];
  const queue = [root];
 
  for (let i = 0; i < queue.length; i++) {
    const node = queue[i];
    result.push(node.val);
 
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
 
  return result;
}

• 🟡 102. Binary Tree Level Order Traversal

Типовые паттерны для Binary Tree

1. Максимальная глубина (высота)

Postorder — вычисляем после детей

var maxDepth = function(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};

• 🟢 104. Maximum Depth of Binary Tree
• 🟢 111. Minimum Depth of Binary Tree

2. Диаметр дерева

Паттерн: на каждом узле считаем высоту + обновляем глобальный максимум

var diameterOfBinaryTree = function(root) {
  let diameter = 0;
 
  function height(node) {
    if (!node) return 0;
 
    const leftH = height(node.left);
    const rightH = height(node.right);
 
    // Обновляем диаметр через этот узел
    diameter = Math.max(diameter, leftH + rightH);
 
    return 1 + Math.max(leftH, rightH);
  }
 
  height(root);
  return diameter;
};

• 🟢 543. Diameter of Binary Tree
• 🔴 124. Binary Tree Maximum Path Sum

3. Инвертирование дерева

Preorder или Postorder — меняем left↔right

var invertTree = function(root) {
  if (!root) return null;
 
  // Swap
  [root.left, root.right] = [root.right, root.left];
 
  invertTree(root.left);
  invertTree(root.right);
 
  return root;
};

• 🟢 226. Invert Binary Tree

4. Симметричное дерево

Паттерн: сравниваем зеркальные узлы

var isSymmetric = function(root) {
  function isMirror(left, right) {
    if (!left && !right) return true;
    if (!left || !right) return false;
 
    return left.val === right.val
      && isMirror(left.left, right.right)
      && isMirror(left.right, right.left);
  }
 
  return isMirror(root, root);
};

• 🟢 101. Symmetric Tree
• 🟢 100. Same Tree

5. Path Sum

DFS с накоплением суммы

var hasPathSum = function(root, targetSum) {
  if (!root) return false;
 
  // Лист — проверяем сумму
  if (!root.left && !root.right) {
    return root.val === targetSum;
  }
 
  const remaining = targetSum - root.val;
  return hasPathSum(root.left, remaining) 
    || hasPathSum(root.right, remaining);
};

• 🟢 112. Path Sum
• 🟡 113. Path Sum II
• 🟡 437. Path Sum III

6. Lowest Common Ancestor (LCA)

Postorder — находим в детях, решаем снизу вверх

var lowestCommonAncestor = function(root, p, q) {
  if (!root || root === p || root === q) return root;
 
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
 
  // Если оба нашлись в разных ветках — текущий узел и есть LCA
  if (left && right) return root;
 
  // Иначе возвращаем того, кто нашёлся
  return left || right;
};

• 🟡 236. Lowest Common Ancestor of a Binary Tree
• 🟡 235. Lowest Common Ancestor of a Binary Search Tree

7. Right Side View

BFS с отслеживанием последнего узла на уровне

var rightSideView = function(root) {
  if (!root) return [];
 
  const result = [];
  const queue = [root];
 
  while (queue.length > 0) {
    const levelSize = queue.length;
 
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
 
      // Последний узел уровня
      if (i === levelSize - 1) {
        result.push(node.val);
      }
 
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
 
  return result;
};

• 🟡 199. Binary Tree Right Side View
• 🟡 513. Find Bottom Left Tree Value

8. Serialize & Deserialize

Preorder для сериализации

var serialize = function(root) {
  const result = [];
 
  function preorder(node) {
    if (!node) {
      result.push('null');
      return;
    }
    result.push(node.val);
    preorder(node.left);
    preorder(node.right);
  }
 
  preorder(root);
  return result.join(',');
};
 
var deserialize = function(data) {
  const values = data.split(',');
  let index = 0;
 
  function build() {
    if (values[index] === 'null') {
      index++;
      return null;
    }
 
    const node = new TreeNode(parseInt(values[index++]));
    node.left = build();
    node.right = build();
    return node;
  }
 
  return build();
};

• 🔴 297. Serialize and Deserialize Binary Tree
• 🟡 449. Serialize and Deserialize BST

9. Построение дерева из массивов

Preorder + Inorder → Tree

var buildTree = function(preorder, inorder) {
  if (preorder.length === 0) return null;
 
  const rootVal = preorder[0];
  const root = new TreeNode(rootVal);
  const mid = inorder.indexOf(rootVal);
 
  root.left = buildTree(
    preorder.slice(1, mid + 1),
    inorder.slice(0, mid)
  );
  root.right = buildTree(
    preorder.slice(mid + 1),
    inorder.slice(mid + 1)
  );
 
  return root;
};

• 🟡 105. Construct Binary Tree from Preorder and Inorder Traversal
• 🟡 106. Construct Binary Tree from Inorder and Postorder Traversal

---

N-ary Tree (произвольное количество детей)

Структура узла

function Node(val, children) {
  this.val = val;
  this.children = children || [];
}

Обходы N-ary

Preorder

var preorder = function(root) {
  const result = [];
 
  function traverse(node) {
    if (!node) return;
    result.push(node.val);
    for (const child of node.children) {
      traverse(child);
    }
  }
 
  traverse(root);
  return result;
};

• 🟢 589. N-ary Tree Preorder Traversal

Postorder

var postorder = function(root) {
  const result = [];
 
  function traverse(node) {
    if (!node) return;
    for (const child of node.children) {
      traverse(child);
    }
    result.push(node.val);
  }
 
  traverse(root);
  return result;
};

• 🟢 590. N-ary Tree Postorder Traversal

Level Order

var levelOrder = function(root) {
  if (!root) return [];
 
  const result = [];
  const queue = [root];
 
  while (queue.length > 0) {
    const levelSize = queue.length;
    const level = [];
 
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      queue.push(...node.children);
    }
 
    result.push(level);
  }
 
  return result;
};

• 🟡 429. N-ary Tree Level Order Traversal

Максимальная глубина N-ary

var maxDepth = function(root) {
  if (!root) return 0;
 
  let max = 0;
  for (const child of root.children) {
    max = Math.max(max, maxDepth(child));
  }
 
  return 1 + max;
};

• 🟢 559. Maximum Depth of N-ary Tree

---

Сложности (Time & Space)

DFS (рекурсивный)

• Time: O(n) — посещаем каждый узел один раз
• Space: O(h) — стек рекурсии, где h = высота дерева
  • Сбалансированное: O(log n)
  • Худший случай (список): O(n)

BFS

• Time: O(n) — посещаем каждый узел один раз
• Space: O(w) — очередь, где w = максимальная ширина уровня
  • Худший случай: O(n) для полного дерева на последнем уровне

---

Мини-шпаргалка: какой паттерн выбрать?

Задача	Паттерн	Ключ
Отсортированный порядок в BST	Inorder DFS	left→node→right
Минимальная разница в BST	Inorder + prev	Соседи в sorted
K-й элемент в BST	Inorder + counter	Остановка на k-м
Высота/глубина	Postorder DFS	Вычисляем после детей
Диаметр	Postorder + global max	Высота + макс путь
Копирование структуры	Preorder DFS	Узел до детей
Удаление дерева	Postorder DFS	Дети до узла
По уровням	BFS	Очередь
Path sum	DFS + accumulator	Передаём остаток
LCA	Postorder DFS	Решаем снизу вверх
Симметрия	Зеркальная рекурсия	Сравниваем left↔right
Валидация BST	Inorder + prev ИЛИ диапазоны	Глобальная проверка

---

Шпаргалка: задача → паттерн → ключ

Задача	Паттерн	Ключ
Отсортированный порядок в BST	Inorder DFS	left→node→right
Минимальная разница в BST	Inorder + prev	Соседи в sorted
K-й элемент в BST	Inorder + counter	Остановка на k-м
Высота/глубина	Postorder DFS	Вычисляем после детей
Диаметр	Postorder + global max	Высота + макс путь
Копирование структуры	Preorder DFS	Узел до детей
Удаление дерева	Postorder DFS	Дети до узла
По уровням	BFS	Очередь
Path sum	DFS + accumulator	Передаём остаток
LCA	Postorder DFS	Решаем снизу вверх
Симметрия	Зеркальная рекурсия	Сравниваем left↔right
Валидация BST	Inorder + prev ИЛИ диапазоны	Глобальная проверка

Типичные ошибки

BST

• ❌ Локальная проверка BST (left.val < node.val < right.val) — не учитывает глубокие поддеревья
• ✅ Использовать диапазоны (min, max) или prev в inorder

Binary Tree

• ❌ Использовать queue.shift() в цикле без причины — O(n) на каждый shift в JS
• ✅ Использовать индекс for (let i = 0; i < queue.length; i++) или shift только для level-разделения
• ❌ Забывать про null-checks перед обращением к .left/.right
• ✅ Всегда проверять if (!node) return ...

Общее

• ❌ Путать preorder/inorder/postorder — важно понимать порядок visit
• ✅ Визуализировать на бумаге порядок посещения для конкретного примера
• ❌ Смешивать DFS и BFS без понимания разницы в Space complexity
• ✅ DFS экономит память на узких деревьях, BFS — на широких

---

Полезные ссылки

• Visualgo — Tree Visualization
• LeetCode Tree Tag
• LeetCode BST Tag