Searching a Component Tree

A component tree — the nested structure a UI framework renders from, or a DOM subtree you're inspecting programmatically — gets searched constantly: "find the node with this id," "get the breadcrumb path to this item," "find every node matching this condition." All three are DFS with a small twist, and this lesson works through each twist explicitly.

Find by id, stopping at the first match

const componentTree = {
  id: "app",
  children: [
    { id: "sidebar", children: [
      { id: "nav-item-1", children: [] },
      { id: "nav-item-2", children: [] },
    ]},
    { id: "main", children: [
      { id: "header", children: [] },
      { id: "content", children: [
        { id: "widget-a", children: [] },
      ]},
    ]},
  ],
};
 
function findById(node, targetId) {
  if (node.id === targetId) return node;
 
  for (const child of node.children) {
    const found = findById(child, targetId);
    if (found) return found; // stop as soon as a branch reports success
  }
 
  return null; // exhausted this node's whole subtree, no match
}

This is plain DFS, with one addition: the moment a recursive call returns a non-null result, propagate it up immediately instead of continuing to check siblings. Crucially, there's no ordering property to exploit here — a component tree isn't a binary search tree, an id isn't "smaller" or "larger" than another in any way that tells you which subtree to skip. That means, in the worst case (the target is the very last node checked, or doesn't exist at all), every node must be visited: O(n), not O(log n). It's worth being explicit about this, because "searching a tree" sounds like it should always be logarithmic — it's only logarithmic when there's an ordering guarantee to exploit, which a general component tree doesn't have.

Computing a breadcrumb path: backtracking

A common companion feature — "show the path from the root to the found node" — needs the search to track where it's been, and specifically to un-track it when a branch doesn't pan out:

function findPath(node, targetId, path = []) {
  path.push(node.id); // tentatively include this node in the path
 
  if (node.id === targetId) return [...path]; // found it — this is the real path
 
  for (const child of node.children) {
    const found = findPath(child, targetId, path);
    if (found) return found; // a deeper call found it — propagate up
  }
 
  path.pop(); // this node's subtree had no match — undo the tentative inclusion
  return null;
}
 
findPath(componentTree, "widget-a");
// ["app", "main", "content", "widget-a"]

This is the backtracking pattern: path.push(...) before recursing, path.pop() after recursing if that branch didn't succeed. Trace it mentally on the tree above: when the search descends into sidebar and finds nothing, path needs "sidebar" removed before trying main — otherwise the final path for widget-a would incorrectly include "sidebar" as if the search had walked through it on the way to the real answer. The push/pop pair is what keeps path an accurate reflection of "the route actually taken to the match," not "every branch that was ever explored."

Collecting every match, not just the first

A third variant — "find every widget," not just one — genuinely cannot stop early, because stopping risks missing a later match:

function findAll(node, predicate, results = []) {
  if (predicate(node)) results.push(node);
  for (const child of node.children) {
    findAll(child, predicate, results);
  }
  return results;
}
 
findAll(componentTree, (node) => node.id.startsWith("nav-item"));
// [{id: "nav-item-1", ...}, {id: "nav-item-2", ...}]

Both findAll and findById's worst case are O(n) — the difference is only in the best and average case: findById can return the moment it finds a match anywhere in the tree, while findAll is committed to visiting every node no matter what, since an earlier return would risk skipping a real match later in the traversal. This is the best/average/worst-case distinction — introduced early in this course — showing up concretely: same worst-case Big-O, genuinely different typical-case behavior.

What to remember

• Searching a general tree by id (no ordering property to exploit) is O(n) worst case — a fundamentally different complexity result from BST search, which is O(log n) specifically because of its ordering invariant.
• A breadcrumb-path search uses the backtracking pattern: push the current node before recursing, pop it back off after recursing if that branch didn't find the target — this keeps the tracked path accurate.
• Collecting every match can't stop early the way a first-match search can, even though both share the same O(n) worst-case bound — the difference is in typical-case behavior, not the worst case.
• These three variants — first match, path to a match, all matches — are the same DFS skeleton with a different rule for when to stop or what to track, not three separate algorithms to memorize.