Component Tree Search

Single-pass collector

TimeO(n)SpaceO(h)Good solution

Single pass over the tree. No intermediate full flatten: only matching nodes are added to the collector, so space is O(k) for the result (and O(h) stack depth). Optimal for this problem.

Code

1interface ComponentNode {
2    id: string
3    type: string
4    children?: ComponentNode[]
5}
6
7const tree: ComponentNode = {
8    id: "root",
9    type: "Page",
10    children: [
11        {
12            id: "header",
13            type: "Header",
14            children: [
15                { id: "logo", type: "Image" },
16                { id: "nav", type: "Nav" }
17            ]
18        },
19        {
20            id: "content",
21            type: "Section",
22            children: [
23                { id: "hero", type: "Image" },
24                { id: "cta", type: "Button" }
25            ]
26        }
27    ]
28}
29
30function findComponentsByType(
31    tree: ComponentNode,
32    targetType: string
33): ComponentNode[] {
34    const result: ComponentNode[] = []
35
36    function visit(node: ComponentNode) {
37        if (node.type === targetType) {
38            result.push(node)
39        }
40        if (node.children) {
41            for (const child of node.children) {
42                visit(child)
43            }
44        }
45    }
46
47    visit(tree)
48    return result
49}
50
51console.log(findComponentsByType(tree, "Button"))
52

Animation

Component tree

Pageroot

Headerheader

Imagelogo

Navnav

Sectioncontent

Imagehero

Buttoncta

Matches (collector)

—

Speed: