re:re:actable
Урок 023 минуты чтения

Задача: обход DOM-дерева

На этой странице
Кратко

Задачи на обход DOM проверяют умение работать с деревом: написать свой getElementsByClassName (обход в глубину по children), найти ближайшего общего предка двух узлов, найти соответствующий узел в копии дерева (по пути индексов), посчитать глубину или собрать все текстовые узлы. Все они решаются DFS/BFS по дереву — рекурсией или стеком — и не требуют знания редких API.

Вопрос

Реализуйте getElementsByClassName(root, className) без встроенных методов поиска, функцию поиска ближайшего общего предка двух элементов и функцию, которая находит в клоне дерева узел, соответствующий узлу из оригинала.

getElementsByClassName

function getElementsByClassName(root, className) {
  const result = [];
 
  function walk(element) {
    for (const child of element.children) {           // только элементы, без текстовых узлов
      if (child.classList.contains(className)) result.push(child);
      walk(child);
    }
  }
 
  walk(root);
  return result;
}

Итеративный вариант (без риска переполнения стека):

function getElementsByClassNameIterative(root, className) {
  const result = [];
  const stack = [...root.children].reverse();
 
  while (stack.length) {
    const el = stack.pop();
    if (el.classList.contains(className)) result.push(el);
    stack.push(...[...el.children].reverse());        // reverse сохраняет порядок документа
  }
 
  return result;
}

Вариант с несколькими классами ("btn primary") — проверять каждый класс через every.

Ближайший общий предок

function commonAncestor(a, b) {
  const ancestors = new Set();
  for (let node = a; node; node = node.parentElement) ancestors.add(node);
  for (let node = b; node; node = node.parentElement) {
    if (ancestors.has(node)) return node;
  }
  return null;
}

O(глубина). Если один узел — предок другого, вернется он сам. Встроенный способ проверить вложенность — a.contains(b).

Соответствующий узел в клоне

function getPath(root, node) {
  const path = [];
  for (let current = node; current !== root; current = current.parentNode) {
    path.unshift([...current.parentNode.childNodes].indexOf(current));
  }
  return path;
}
 
function findByPath(root, path) {
  return path.reduce((node, index) => node.childNodes[index], root);
}
 
function findCorresponding(rootA, rootB, nodeA) {
  return findByPath(rootB, getPath(rootA, nodeA));
}
 
const clone = document.body.cloneNode(true);
const original = document.querySelector("#price");
findCorresponding(document.body, clone, original);  // тот же элемент в копии

Собрать текст и посчитать глубину

function collectText(node) {
  if (node.nodeType === Node.TEXT_NODE) return node.textContent;
  return [...node.childNodes].map(collectText).join("");   // то же делает node.textContent
}
 
function maxDepth(element) {
  if (element.children.length === 0) return 1;
  return 1 + Math.max(...[...element.children].map(maxDepth));
}

Встроенный TreeWalker

const walker = document.createTreeWalker(document.body, NodeFilter.SHOW_TEXT);
const texts = [];
while (walker.nextNode()) texts.push(walker.currentNode.textContent.trim());

Доп. вопросы интервьюера

  • children vs childNodes? children — только элементы, childNodes — также текст и комментарии.
  • HTMLCollection vs NodeList? getElementsBy* возвращают «живую» коллекцию, querySelectorAll — статический NodeList.
  • DFS или BFS? DFS — порядок документа; BFS (очередь) — по уровням, например найти ближайший к корню элемент.
  • Сложность? O(n) по числу узлов.

Что важно помнить

  • Решение — обычный обход дерева; DOM — частный случай дерева.
  • Сохраняйте порядок документа, если это важно для задачи.
  • Для глубоких деревьев используйте итеративный обход.
  • Теория: DFS и BFS для дерева.

Мини-шпаргалка

Поиск по классу: DFS по children + classList.contains. Общий предок: Set предков первого узла, подъем от второго. Узел в клоне: путь индексов childNodes от корня. children — элементы, childNodes — все узлы. Встроенно — TreeWalker, contains.

Документация

MDN: Element.children, MDN: Node.childNodes, MDN: Document.createTreeWalker(), MDN: Node.contains().

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам