Graph Valid Tree - Practice Coding Problems

Graph Valid Tree - Problem

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

A valid tree must satisfy two conditions:

All nodes are connected (exactly one connected component)
There are no cycles in the graph

For a tree with n nodes, there must be exactly n-1 edges.

Input & Output

Example 1 — Valid Tree

$ Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,4]]

› Output: true

💡 Note: The graph forms a valid tree: 5 nodes with 4 edges, all connected, no cycles. Node 1 connects to nodes 0, 2, and 4, creating a tree structure.

Example 2 — Has Cycle

$ Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,4],[3,4]]

› Output: false

💡 Note: The graph contains a cycle: 1→4→3→2→1. A valid tree cannot have cycles.

Example 3 — Disconnected

$ Input: n = 4, edges = [[0,1],[2,3]]

› Output: false

💡 Note: The graph has 2 disconnected components: {0,1} and {2,3}. A tree must be fully connected.

Constraints

1 ≤ n ≤ 2000
0 ≤ edges.length ≤ 5000
edges[i].length == 2
0 ≤ ai, bi < n
ai ≠ bi
There are no self-loops or repeated edges.

Visualization

Tap to expand

Key Insight: Tree = Connected + Acyclic + Exactly n-1 edges

Understanding the Visualization

Input Graph

Given n nodes and edges list

Tree Properties

Check: exactly n-1 edges, connected, no cycles

Output

Return true if valid tree, false otherwise

Key Takeaway

🎯 Key Insight: A valid tree has exactly n-1 edges, is fully connected, and contains no cycles

Asked in

G Google 45 f Facebook 38 a Amazon 32 M Microsoft 28

The key insight is that a valid tree must have exactly n-1 edges, be fully connected, and contain no cycles. Best approach is Union-Find which efficiently detects cycles during construction. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Paths	O(n²)	O(n)	Build adjacency list and check all possible paths for cycles
DFS with Edge Count Check	O(n)	O(n)	Check edge count first, then use DFS to verify connectivity
Union-Find (Disjoint Set)	O(n)	O(n)	Use Union-Find to efficiently detect cycles and check connectivity

Brute Force - Check All Paths — Algorithm Steps

Build adjacency list from edges
Use DFS to detect cycles by tracking parent nodes
Check if all nodes are connected in one component

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create adjacency list from edges

DFS Traversal

Visit nodes while tracking parent to avoid false cycles

Check Result

Verify all nodes visited and no cycles found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_N 2000

int graph[MAX_N][MAX_N];
int graphSize[MAX_N];
bool visited[MAX_N];
int visitedCount = 0;

bool dfs(int node, int parent, int n) {
    if (visited[node]) {
        return false;
    }
    
    visited[node] = true;
    visitedCount++;
    
    for (int i = 0; i < graphSize[node]; i++) {
        int neighbor = graph[node][i];
        if (neighbor != parent) {
            if (!dfs(neighbor, node, n)) {
                return false;
            }
        }
    }
    return true;
}

bool solution(int n, int edges[][2], int edgesSize) {
    if (edgesSize != n - 1) {
        return false;
    }
    
    // Initialize graph
    for (int i = 0; i < n; i++) {
        graphSize[i] = 0;
        visited[i] = false;
    }
    visitedCount = 0;
    
    // Build adjacency list
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        graph[u][graphSize[u]++] = v;
        graph[v][graphSize[v]++] = u;
    }
    
    if (!dfs(0, -1, n)) {
        return false;
    }
    
    return visitedCount == n;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    fgets(line, sizeof(line), stdin); // consume newline
    fgets(line, sizeof(line), stdin);
    
    // Parse edges
    int edges[MAX_N][2];
    int edgesSize = 0;
    
    if (strcmp(line, "[]\n") != 0) {
        char* ptr = line + 1; // skip '['
        while (*ptr && *ptr != ']') {
            if (*ptr == '[') {
                ptr++;
                int u = strtol(ptr, &ptr, 10);
                ptr++; // skip ','
                int v = strtol(ptr, &ptr, 10);
                edges[edgesSize][0] = u;
                edges[edgesSize][1] = v;
                edgesSize++;
                ptr++; // skip ']'
                if (*ptr == ',') ptr++;
            } else {
                ptr++;
            }
        }
    }
    
    printf(solution(n, edges, edgesSize) ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

DFS visits each node and edge multiple times in worst case

⚠ Quadratic Growth

Space Complexity

O(n)

Adjacency list storage and recursion stack

⚡ Linearithmic Space

125.0K Views

High Frequency

~25 min Avg. Time

1.6K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Paths — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler