How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Check path in N-ary tree | Amazon Coding Question

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.

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

Expected Output: False

Explanation: Prefix [1,2] matches at node 1, but neither child (values 4, 5) equals 99.

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

Expected Output: False

Explanation: The path must start at the root whose value is 1, not 2, so no anchored match exists.

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

Expected Output: True

Explanation: A linear chain of repeated value 5: root -> 1 -> 2 matches [5,5,5]. Duplicate values must still be traversed correctly.

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

Expected Output: True

Explanation: Root (value 5) has two children: node 1 (value 5) and node 3 (value 7). Matching [5,7] requires choosing the branch to node 3, not node 1 — backtracking across same-prefix branches.

Input: ([1], [[]], [1])

Expected Output: True

Explanation: Single-node tree, path of length 1 matching the root value.

Input: ([1], [[]], [])

Expected Output: True

Explanation: Empty path matches trivially regardless of the (non-empty) tree.

Input: ([], [], [1])

Expected Output: False

Explanation: Empty tree cannot match a non-empty path.

Input: ([], [], [])

Expected Output: True

Explanation: Empty tree and empty path both vacuously match.

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

Expected Output: False

Explanation: The path is longer than any available branch from the matching prefix; node 3 (value 4) has no children, so it cannot extend to 9.

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

Expected Output: True

Explanation: Negative and repeated values: chain -3 -> -3 -> 4 matches the full path.

Hints

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

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.