Intuition

A graph is a tree iff it has exactly n - 1 edges AND is connected. Those two conditions together forbid both cycles and disconnection.

Approach

If the edge count is not n-1, it cannot be a tree.
Otherwise count connected components with union-find.
It is a valid tree iff there is exactly one component.

Complexity

Time — O((V+E) alpha): union-find over the edges.
Space — O(V): parent array.

Common Pitfalls

The n-1 edge check alone is not enough — you also need connectivity.

Full Solution — all languages

class Solution:
    def validTree(self, n, edges):
        if len(edges)!=n-1: return False
        par=list(range(n))
        def find(x):
            while par[x]!=x:
                par[x]=par[par[x]]; x=par[x]
            return x
        comp=n
        for a,b in edges:
            ra,rb=find(a),find(b)
            if ra==rb: return False
            par[ra]=rb; comp-=1
        return comp==1

import java.util.*;

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if(edges.length!=n-1)return false; int[] par=new int[n]; for(int i=0;i<n;i++)par[i]=i; int comp=n; for(int[] e:edges){int ra=find(par,e[0]),rb=find(par,e[1]); if(ra==rb)return false; par[ra]=rb;comp--;} return comp==1;
    }
    int find(int[] par,int x){while(par[x]!=x){par[x]=par[par[x]];x=par[x];}return x;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        if((int)edges.size()!=n-1)return false; vector<int> par(n); for(int i=0;i<n;i++)par[i]=i; function<int(int)> find=[&](int x){while(par[x]!=x){par[x]=par[par[x]];x=par[x];}return x;}; int comp=n; for(auto& e:edges){int ra=find(e[0]),rb=find(e[1]); if(ra==rb)return false; par[ra]=rb;comp--;} return comp==1;
    }
};

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {boolean}
 */
var validTree = function(n, edges) {
    if(edges.length!==n-1)return false; const par=[]; for(let i=0;i<n;i++)par[i]=i; function find(x){while(par[x]!==x){par[x]=par[par[x]];x=par[x];}return x;} let comp=n; for(const e of edges){const ra=find(e[0]),rb=find(e[1]); if(ra===rb)return false; par[ra]=rb;comp--;} return comp===1;
};

Graph Valid Tree

Example 1

Example 2

Constraints