Valid BFS? — Editorial

Opening the reading…

Intuitionturning arbitrary neighbor choices into one canonical BFS

A BFS removes vertices in queue order. When it removes a vertex, all of that vertex's unvisited children enter the queue together, in any order. Therefore, the only freedom is the order in which siblings are appended. A child can never be removed before an already queued sibling, because the sibling is closer to the front of the queue.

The proposed order tells you how every group of siblings should be arranged: among the unvisited neighbors of a vertex, earlier positions should be appended first. Record those positions, sort every adjacency list by them, and run BFS. This creates the earliest possible BFS sequence consistent with the proposed local choices. If even this forced arrangement does not produce the proposed order, no other arrangement can.

A deeper child waits behind siblings that were already appended to the queue.

Approachmake the proposed order the tie-breaker everywhere

Reject the order unless its first vertex is 1, because every BFS in the problem starts by placing vertex 1 in the queue.

Build the undirected adjacency lists, adding each edge in both directions, because BFS must be able to inspect every neighbor from either endpoint.

Record position[v] for every vertex v in the proposed order, because comparing positions lets you decide which sibling must be appended first in constant time.

Sort each adjacency list by position, because this chooses the only locally compatible order that can make the proposed sequence as early as possible.

Start BFS with vertex 1 marked used before it is removed, because marking on enqueue prevents the undirected edge back to a parent from adding that parent again.

Remove vertices from the queue and append every unvisited neighbor in the sorted order, because this simulates the BFS whose choices are most favorable to the proposed permutation.

Compare the produced sequence with order, because matching the canonical sequence proves the proposed order is achievable, while any mismatch means no alternative sibling ordering can repair it.

Complexitysorting dominates the linear traversal

MEASURE	BOUND	WHY
Time	O(n log n)	The total sorting work is sum over vertices of O(deg(v) log deg(v)), which is at most O(n log n) because the tree has 2n - 2 adjacency entries. BFS then examines each entry once, adding O(n).
Space	O(n) extra	The graph stores 2n - 2 directed adjacency entries, while position, used, produced, and the queue are all linear in n. The returned value is only a boolean, so there is no output array to exclude. A path-shaped tree still uses O(n) storage, although its sorted lists are tiny.

Here n is the number of vertices, and deg(v) is the degree of vertex v.

Annotated solutionC++ · position-sorted adjacency lists followed by BFS

CPPComplete solution: sort neighbors by proposed positions, simulate BFS, and compare the result.

#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

class Solution {
public:
    bool validBFS(vector<vector<int>> edges, vector<int> order) {
        int n = static_cast<int>(order.size());
        if (n == 0 || order[0] != 1) {
            return false;
        }

        vector<vector<int>> graph(n + 1);
        for (const vector<int>& edge : edges) {
            if (edge.size() != 2) {
                return false;
            }

            int u = edge[0];
            int v = edge[1];
            if (u < 1 || u > n || v < 1 || v > n) {
                return false;
            }

            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        vector<int> position(n + 1, -1);
        for (int i = 0; i < n; ++i) {
            int v = order[i];
            if (v < 1 || v > n || position[v] != -1) {
                return false;
            }
            position[v] = i;
        }

        for (int v = 1; v <= n; ++v) {
            sort(graph[v].begin(), graph[v].end(),
                 [&](int a, int b) {
                     return position[a] < position[b];
                 });
        }

        vector<int> produced;
        produced.reserve(n);
        vector<char> used(n + 1, 0);
        queue<int> q;

        q.push(1);
        used[1] = 1;

        while (!q.empty()) {
            int v = q.front();
            q.pop();
            produced.push_back(v);

            for (int u : graph[v]) {
                if (!used[u]) {
                    used[u] = 1;
                    q.push(u);
                }
            }
        }

        return produced == order;
    }
};

The important placement is used[u] = 1 when u enters the queue, not when it leaves. In an undirected tree, a vertex is adjacent to its parent, so waiting until dequeue time leaves a window where another inspection can enqueue it again. Marking on enqueue matches the statement's definition of visited and keeps every vertex in the queue exactly once.

Sorting does not claim that the original BFS used a particular neighbor order. It constructs the most favorable order for the proposed sequence: every child is placed before any sibling that appears later in order. The final comparison is therefore decisive. A mismatch is not merely a poor simulation choice; it means the queue rules force a different removal order.