Validate BFS order queries on a tree

Q: Validate BFS order queries on a tree

This question evaluates understanding of BFS traversal, tree graph representation, and the ability to reason about allowable dequeue/enqueue orderings in a FIFO queue.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Rubrik.

Q: What role is this question designed for?

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

Question

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

Validate BFS order queries on a tree

Quick Overview

Comments (0)