Check path in N-ary tree

Given the root of an N-ary tree and a sequence of integers path[0..k-1], determine whether there exists a path starting at the root whose node values match the sequence in order. Node values are not guaranteed to be unique, and the matching path does not need to end at a leaf. Describe your algorithm, analyze time and space complexity, and provide code.

Check Path in N-ary Tree

Given the root of an N-ary tree and a sequence of integers path[0..k-1], determine whether there exists a path starting at the root whose node values match the sequence in order. Node values are not guaranteed to be unique, and the matching path does not need to end at a leaf.

The tree is provided in a flat, array-based form so it is easy to pass to your function:

• values: an array of integers where values[i] is the value of node i. The root is node 0. If values is empty, the tree is empty.
• children: an array of integer arrays where children[i] lists the node ids of the direct children of node i (in order).
• path: the sequence of integers to match, starting at the root.

Return true if some root-anchored downward path (root = first element, each subsequent element a child of the previous) has node values exactly equal to path in order; otherwise return false.

Notes:

• The path must start at the root. An empty path matches trivially (return true) as long as you treat the empty-prefix match as valid.
• The path does NOT need to reach a leaf — it can stop at any depth.
• Because values may repeat, you may need to explore multiple branches that share the same prefix value.

Example: with values = [1,2,3,4,5] and children = [[1,2],[3,4],[],[],[]] (root 1 has children 2 and 3; node 2 has children 4 and 5), path = [1,2,4] returns true (root 0 -> child 1 -> child 3), while path = [2,4] returns false (must start at root value 1).

Constraints

• 0 <= number of nodes N <= 10^4
• 0 <= len(path) <= 10^4
• Node values fit in a 32-bit signed integer (may be negative).
• Node values are NOT guaranteed to be unique.
• children[i] contains valid node ids in the range [0, N-1]; the structure forms a tree rooted at node 0.
• An empty path matches trivially (return true).

Hints

1. The path is anchored at the root, so the first element of path must equal values[0]; if not, the answer is immediately false (unless the path is empty).
2. Use DFS from the root carrying the current index into path. At each node, check its value against path[idx]; if it matches and idx is the last index, you are done. Otherwise recurse into the node's children with idx+1.
3. Because values can repeat, a single value match is not enough — you must try every child branch that continues the prefix, returning true as soon as any branch completes the full path.
4. Handle the empty-tree and empty-path boundaries explicitly: an empty path is a trivial match, and an empty tree only matches an empty path.