Katkat
Back

Validate BFS order queries on a tree

RubrikSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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:

  • The BFS start node is order[0].
  • BFS uses a FIFO queue.
  • When a node is dequeued, you may enqueue its unvisited neighbors in any order (i.e., neighbor iteration order is not fixed).
  • The BFS output is the dequeue order.

Return a boolean for each query.

Example:

  • u = [1, 1, 4], v = [3, 2, 3] defines edges (1,3), (1,2), (4,3).
  • For 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).