Root-started value path in an N-ary tree

The path must start at the root and follow parent-to-child edges, one value per level. It may stop at any node, not only a leaf. Values can repeat, so one node can have several children with the next value, and only one of them may lead on to the rest of the path. You cannot pick a child greedily; you must keep every candidate alive.

Brute force. List every root-to-node path and check whether any of them equals path. A tree can hold O(N) such paths, each up to O(depth) long, so this is O(N · depth). It is also wasteful, because it never uses the path to prune.

DFS with backtracking. Recurse from the root with an index i. If node.val != path[i], fail. If i is the last index, succeed. Otherwise try every child with i + 1 and return true if any child succeeds. Each node is reached at most once (its depth fixes the index it is compared to), so this is O(N). In Python, a deep tree can hit the recursion limit, so it is better to write it without recursion.

Level frontier (the version to write). Keep frontier: the nodes at depth i whose root-to-node values equal path[0..i]. Start with [root] if root.val == path[0]. To advance, keep the children of frontier nodes whose value is path[i + 1]. If the frontier becomes empty, the path does not exist. If it survives all len(path) steps, the path exists.

Invariant: after step i, frontier holds exactly the nodes whose root-to-node path spells path[0..i]. Every node is at one depth, so it enters a frontier at most once. Total work is O(N), and the loop also stops after len(path) levels even when the tree is deeper.

The same loop returns a concrete path if you store a parent pointer with each frontier entry. That is the most common follow-up.

from __future__ import annotations

from dataclasses import dataclass, field
from typing import Optional


@dataclass
class Node:
    val: int
    children: list["Node"] = field(default_factory=list)


def path_exists(root: Optional[Node], path: list[int]) -> bool:
    """True if some root-started downward path has exactly these values."""
    if root is None or not path or root.val != path[0]:
        return False
    frontier = [root]
    for want in path[1:]:
        frontier = [c for node in frontier for c in node.children if c.val == want]
        if not frontier:
            return False
    return True


def find_path(root: Optional[Node], path: list[int]) -> Optional[list[Node]]:
    """Return one matching list of nodes (root first), or None."""
    if root is None or not path or root.val != path[0]:
        return None
    # Each entry: (node, index of its parent entry in the previous level).
    levels: list[list[tuple[Node, int]]] = [[(root, -1)]]
    for want in path[1:]:
        nxt = [
            (child, p)
            for p, (node, _) in enumerate(levels[-1])
            for child in node.children
            if child.val == want
        ]
        if not nxt:
            return None
        levels.append(nxt)
    # Walk the parent pointers back from any survivor.
    out: list[Node] = []
    idx = 0
    for level in reversed(levels):
        node, parent = level[idx]
        out.append(node)
        idx = parent
    out.reverse()
    return out


if __name__ == "__main__":
    #        1
    #     /  |  \
    #    2   3   2
    #   /        |  \
    #  4         5   4
    #            |
    #            6
    tree = Node(1, [
        Node(2, [Node(4)]),
        Node(3),
        Node(2, [Node(5, [Node(6)]), Node(4)]),
    ])
    assert path_exists(tree, [1])
    assert path_exists(tree, [1, 2, 4])
    assert path_exists(tree, [1, 2, 5, 6])      # only the second 2 works
    assert path_exists(tree, [1, 2, 5])         # stops before a leaf
    assert not path_exists(tree, [1, 3, 5])
    assert not path_exists(tree, [2])           # must start at the root
    assert not path_exists(tree, [1, 2, 5, 6, 7])
    assert not path_exists(None, [1])
    got = find_path(tree, [1, 2, 5, 6])
    assert got is not None and [n.val for n in got] == [1, 2, 5, 6]
    assert got[1] is tree.children[2]
    assert find_path(tree, [1, 4]) is None
    # Deep chain: no recursion limit problems.
    deep = Node(1)
    cur = deep
    for _ in range(10_000):
        cur.children.append(Node(1))
        cur = cur.children[0]
    assert path_exists(deep, [1] * 1000)
    print("ok")

• path_exists: O(N) time in the worst case. Each node is compared at most once, at the level that matches its depth, and the loop stops after len(path) levels. O(W) extra space, where W is the widest frontier (at most the width of the tree).
• find_path: O(N) time. O(sum of frontier sizes) space, up to O(N), because it keeps every level so it can walk back.
• A recursive DFS is also O(N) time, with O(min(depth, len(path))) stack space.

• Tree above, [1] → true (path of length one is just the root).
• [1, 2, 4] → true (through either child valued 2).
• [1, 2, 5, 6] → true; a greedy choice of the first 2 would wrongly return false.
• [1, 2, 5] → true; the path need not end at a leaf.
• [1, 3, 5] → false; 3 has no children.
• [2] → false; the path must start at the root.
• [1, 2, 5, 6, 7] → false; the path is longer than the tree.
• Empty tree, any path → false.
• A single chain of 10,001 nodes all valued 1, path of 1,000 ones → true, with no recursion error.
• Star tree: root with 10,000 children all valued 7, path [root.val, 7] → true; [root.val, 7, 7] → false, after scanning all 10,000 children once.

• Return the matching nodes, or all matching paths. Store a parent index per frontier entry, as find_path does, and walk back. For all paths, walk back from every survivor in the final level. Each survivor gives exactly one path, so there are at most O(N) of them, and the output is O(N · len(path)).
• The path must end at a leaf. Check path_exists as before, then require at least one node in the final frontier to have no children.
• Many queries on one tree. Preprocess each node's children into a dict[int, list[Node]], so each step costs the number of matching children instead of all children. If duplicate siblings are common, merge the tree into a trie keyed by value (combine siblings with equal values and union their subtrees). Then each query is O(len(path)) with one dictionary lookup per step.
• The path may start at any node, not only the root. Run a DFS that keeps, for each node, the set of prefix lengths matched by the path that ends there, and extend it like KMP. Alternatively, keep the root-to-node value stack and run KMP with the failure function of path as you descend (push and pop state when you backtrack). Both are O(N + len(path)).
• Wildcards (* matches any single value, or any run of nodes). A single-node wildcard just keeps all children at that step. A "skip any number of levels" wildcard turns the frontier into a set of (node, index) states, like matching a regex against tree paths; guard with a visited set on (node, index).

Mid-level (L4)

• Asks whether values can repeat and whether the path must end at a leaf.
• Writes a correct DFS that tries every child with a matching value, not only the first.
• Handles the empty tree, a single-node path, and a path longer than the tree.

Senior (L5)

• Explains why the work is O(N): each node is compared once, at its own depth.
• Writes it without recursion, or names the recursion-depth risk for a chain of 10^4 nodes in Python.
• Extends the answer to return the actual nodes without a second traversal.

Staff (L6+)

• Talks about the repeated-query case: index children by value, or build a value trie, and states the tradeoffs in memory and update cost.
• Handles the "start anywhere" version with KMP-style state along the DFS and gives the O(N + L) bound.
• Discusses how the tree arrives (serialized input, streaming, very wide nodes) and how that changes the design.