Quick Overview

This question evaluates understanding of tree traversal and sequence matching in N-ary trees, including handling non-unique node values and maintaining traversal state across branches.

Check path in N-ary tree

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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.

Quick Answer: This question evaluates understanding of tree traversal and sequence matching in N-ary trees, including handling non-unique node values and maintaining traversal state across branches.

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).

Examples

Input: ([1, 2, 3, 4, 5], [[1, 2], [3, 4], [], [], []], [1, 2, 4])

Expected Output: True

Explanation: Root 0 (value 1) -> child node 1 (value 2) -> child node 3 (value 4). Matches [1,2,4].

Input: ([1, 2, 3, 4, 5], [[1, 2], [3, 4], [], [], []], [1, 3])

Expected Output: True

Explanation: Root 0 (value 1) -> child node 2 (value 3). The path stops at a non-leaf depth, which is allowed.

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.

Loading coding console...