Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

BFS with Edge-Count Shortcut#

A graph on n nodes is a valid tree if and only if it is connected and has exactly n-1 edges. The edge-count check is a free O(1) shortcut: fewer than n-1 edges means the graph is definitely disconnected, while more means there is at least one cycle — in either case we return false immediately without any traversal. If the edge count is exactly n-1, we still need to verify connectivity (the n-1 edges might form a forest with multiple components). BFS from node 0 counts how many distinct nodes are reached; if all n nodes are visited the graph is connected and, combined with the edge-count guarantee, is a valid tree. The overall complexity is O(n + e) time and O(n) space for the adjacency list and visited array.

A graph is a valid tree if

• It is connected
• It has no cycles (covers n-1 edges)

bool validTree(int n, vector<vector<int>>& edges) {
    if(edges.size() != n-1)
        return false;

    vector<vector<int>> adj(n);
    for(auto &edge : edges)
    {
        int u = edge[0];
        int v = edge[1];

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

    vector<bool> visited(n, false);
    queue<int> q;
    q.push(0);

    int count = 0;
    while(!q.empty())
    {
        int node = q.front();
        q.pop();
        count++;

        if(visited[node])
            continue;

        visited[node] = true;

        for(int neighbor : adj[node])
        {
            if(!visited[neighbor])
                q.push(neighbor);
        }
    }
    return count==n;
}