Command Palette

Search for a command to run...

Hectal
Problem 23.1 · Cycle DetectionMedium

Graph Valid Tree

PatternUnion-FindGraph DFS and Flood Fill

What it teaches: Tree = n − 1 edges and no cycle (which together imply connected).

Practise it on judges as “Graph Valid Tree”.

The problem

Given n nodes labelled 0..n−1 and a list of undirected edges, return true if the edges form a valid tree.

Example 1

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

Example 2

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

Constraints

  • 1 ≤ n ≤ 2000
  • No duplicate edges or self-loops

Pattern clues in the wording

  • → "Is it a tree?"

These clues point to Union-Find: Keep each group as a tree with a root; find the root to test membership and link roots to merge groups.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public boolean validTree(int n, int[][] edges) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
n = 5
edges = [[0,1],[0,2],[0,3],[1,4]]
true
2
n = 5
edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
false
3
n = 4
edges = [[0,1],[2,3]]
false

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Edge count + union-find · O(n α(n))
1

Edge count + union-find

Time O(n α(n)) Space O(n)

If edges ≠ n − 1, false. Otherwise union every edge; if any edge joins two nodes already connected, false.

Approach 1
class Solution {
    private int[] parent;

    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int[] e : edges) {
            int a = find(e[0]), b = find(e[1]);
            if (a == b) return false;
            parent[a] = b;
        }
        return true;
    }

    private int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
}

Verdict: Short and fast.

Before you submit

Edge cases and common mistakes

Test these inputs

  • n = 1 with no edges (a tree)
  • Right edge count but disconnected with a cycle

Mistakes people make

  • Checking only for cycles (a forest has none but isn't a tree).

Interview

Follow-up questions

How would you do it with DFS?