Solution

We'll collect every descendant of the root once, keep the ones whose ancestor chain satisfies the selector's compounds, and return them in the order we found them.

The problem, in plain English

A selector like .menu ul a is a chain of conditions read outside-in: an <a> that lives inside some <ul> that lives inside something with class menu. Each space is the descendant combinator — "somewhere inside", at any depth. So for each candidate <a> we don't check its parent specifically; we check whether walking up its ancestors we can find a ul, and above that a .menu.

The mental model

Split the selector into compounds on whitespace, then match right to left. The rightmost compound is the cheapest filter — it picks the candidate set (all the as). For each candidate, walk up the parent chain trying to satisfy the remaining compounds in reverse: find the nearest ancestor matching ul, then from there keep climbing to find one matching .menu. Consume all of them and the candidate is a real match.

A first attempt

You might try to match top-down, direct-parent style — for ul a, find each ul, then take its direct <a> children:

function qsaNaive(root, selector) {
  const [outer, inner] = selector.split(' ');
  const out = [];
  for (const anc of collect(root, outer)) {
    for (const child of anc.children) {
      if (child.tagName.toLowerCase() === inner) out.push(child);
    }
  }
  return out;
}

Two problems. It only looks at direct children, so <ul><li><a> is missed — but the descendant combinator allows any depth. And when two uls nest, the same deep <a> gets collected twice and the results come out grouped by ancestor, not in document order. Descendant matching wants "any ancestor above", checked per element, not "direct children of each ancestor".

The working solution

function querySelectorAll(root, selector) {
  const compounds = selector.trim().split(/\s+/);
  const target = compounds[compounds.length - 1];
  const ancestors = compounds.slice(0, -1);

  const results = [];
  for (const el of descendants(root)) {            // document order, once each
    if (matchesCompound(el, target) && hasAncestorChain(el, ancestors, root)) {
      results.push(el);
    }
  }
  return results;
}

// Pre-order DFS over element children — visits parent before children, left
// before right, i.e. document order.
function descendants(root) {
  const out = [];
  (function walk(node) {
    for (const child of node.children) {
      out.push(child);
      walk(child);
    }
  })(root);
  return out;
}

// Consume `compounds` from last to first by walking up (but not past root).
function hasAncestorChain(el, compounds, root) {
  let i = compounds.length - 1;
  let node = el.parentElement;
  while (i >= 0 && node && node !== root) {
    if (matchesCompound(node, compounds[i])) i -= 1; // greedy: nearest ancestor
    node = node.parentElement;
  }
  return i < 0; // every ancestor compound was satisfied
}

function matchesCompound(el, compound) {
  const tokens = compound.match(/[#.]?[\w-]+|\[[^\]]+\]|\*/g) || [];
  return tokens.every((t) => {
    if (t === '*') return true;
    if (t[0] === '#') return el.id === t.slice(1);
    if (t[0] === '.') return el.classList.contains(t.slice(1));
    if (t[0] === '[') {
      const m = t.slice(1, -1).match(/^([\w-]+)(?:=\s*"?([^"]*)"?)?$/);
      if (!m || !el.hasAttribute(m[1])) return false;
      return m[2] === undefined ? true : el.getAttribute(m[1]) === m[2];
    }
    return el.tagName.toLowerCase() === t.toLowerCase();
  });
}

module.exports = { querySelectorAll };

The shifts from the naive version: one flat pass in document order (so results are ordered and each element appears once by construction), matching right-to-left (candidate set first, then verify), and treating the combinator as "any ancestor" via an upward walk rather than direct children.

Walking through one call

querySelectorAll(root, '.menu ul a') on <div class="menu"><ul><li><a>hit</a></li></ul></div><a>miss</a>:

• split → ['.menu', 'ul', 'a']; target a, ancestors ['.menu', 'ul'].
• descendants (document order): div.menu, ul, li, a(hit), a(miss).
• a(hit) — matches target a. Climb: li (no), ul matches ul → i=0, div.menu matches .menu → i=-1. Kept.
• a(miss) — matches target a. Climb: parent is root → loop stops, i still 1. Dropped.
• result → [a(hit)].

Because we filtered a single ordered list, no sort or dedup step is needed.

Gotchas

• Direct children only — using node.children of each ancestor misses deeper descendants. The combinator is "any depth"; walk the whole ancestor chain instead.
• Double-counting nested ancestors — .a .a b with nested .as can push b twice if you iterate per-ancestor. Iterating candidates once and asking "does any valid chain exist?" yields each element once.
• Greedy ancestor consumption is safe here — for pure descendant combinators, taking the nearest matching ancestor for each compound never blocks a valid match; that reasoning breaks the moment you add > (child) combinators.
• Walking past the root — stop the upward walk at root; otherwise a compound could match something outside the intended scope.

Going further

• Child and sibling combinators — >, +, ~ remove the "any depth" freedom, so greedy no longer works; you need backtracking or an explicit combinator step machine.
• Selector lists — a, b (comma) means union; run each selector and merge in document order, deduping.
• The scoping subtlety — the real querySelectorAll lets a leftmost compound match an ancestor above the root element; :scope was added to opt into strict subtree scoping like ours.