This question evaluates understanding of BFS traversal, tree graph representation, and the ability to reason about allowable dequeue/enqueue orderings in a FIFO queue.
You are given an undirected tree described by two equal-length arrays u and v (each of length n-1). For every index i, there is an undirected edge between u[i] and v[i]. The tree contains exactly n distinct node labels (labels are arbitrary integers).
You are also given q queries. Each query is an array order of length n containing each node label exactly once (a permutation).
For each query, decide whether order can be the output of a standard BFS traversal on this tree under the following rules:
order[0]
.
Return a boolean for each query.
Example:
u = [1, 1, 4]
,
v = [3, 2, 3]
defines edges
(1,3), (1,2), (4,3)
.
order = [1,2,3,4]
, the answer is
true
(one valid BFS enqueues
2
then
3
after visiting
1
).
Constraints (typical interview setting):
n
can be up to
2e5
.
q
can be large; aim for better than
O(q * n^2)
.