Root-started value path in an N-ary tree

You are given the root of an N-ary tree (each node has an integer val and a list of children) and a list of integers path.

Return true if there is a downward path that starts at the root, moves from parent to child at each step, and visits nodes whose values are exactly path, in order. The path may stop at any node; it does not have to reach a leaf. Return false otherwise.

Values are not unique: several siblings can share a value, and only some of them may continue the path.

class Node:
    val: int
    children: list["Node"]

def path_exists(root: Node | None, path: list[int]) -> bool: ...

Constraints

• The tree has between 1 and 10^4 nodes.
• Node values are positive integers up to 10^5.
• 1 <= len(path) <= 1000.

Example 1

        1
     /  |  \
    2   3   2
   /        |  \
  4         5   4
            |
            6

• path = [1, 2, 5, 6] → true (through the third child of the root, not the first).
• path = [1, 2, 5] → true (the path may end before a leaf).
• path = [1, 3, 5] → false.

Example 2

Same tree, path = [2, 4] → false, because the path must start at the root.

Be ready to return the matching nodes themselves, not only a boolean.

Reconstructed from the reported question; details may differ from what interviewers ask.