Graph Valid Tree

Medium
443.

Graph Valid Tree

Graph Valid Tree is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google, Meta and LinkedIn interviews.

You have n nodes labelled 0 through n - 1 and a list of undirected edges.

Return true if these edges make a valid tree — connected and acyclic.

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
Explanation
There is a cycle.

Example 3

Input
n = 4, edges = [[0,1],[2,3]]
Output
false
Explanation
Not connected.

Constraints

  • 1 <= n <= 40
  • 0 <= edges.length <= 60
  • There are no duplicate edges and no self-loops.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {boolean}
 */
var validTree = function(n, edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Graph Valid Tree — Solution in Python, Java & C++

Graph Valid Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Graph Valid Tree is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google, Meta and LinkedIn interviews.

Problem statement

You have n nodes labelled 0 through n - 1 and a list of undirected edges.

Return true if these edges make a valid tree — connected and acyclic.

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
Explanation: There is a cycle.

Example 3

Input: n = 4, edges = [[0,1],[2,3]]
Output: false
Explanation: Not connected.

Constraints

  • 1 <= n <= 40
  • 0 <= edges.length <= 60
  • There are no duplicate edges and no self-loops.

Hints for Graph Valid Tree

  1. Hint 1

    A tree on n nodes has exactly n - 1 edges — check that first and you rule out most inputs immediately.

  2. Hint 2

    With the right edge count, connected and acyclic become the same condition.

  3. Hint 3

    So union the edges and reject the moment one joins two nodes already in the same set.

How to solve Graph Valid Tree

A tree on n nodes has exactly n - 1 edges; with that count, connected and acyclic coincide, so union the edges and fail on the first one whose endpoints already share a root.

Approach

  1. Return false unless len(edges) == n - 1.
  2. Union-find over the edges; return false if an edge joins two nodes already connected.
  3. Return true.

Why it works

n - 1 edges with no cycle is a spanning forest with exactly one component — a tree. A cycle is detected precisely when an edge's endpoints are already in the same set.

Complexity

  • Time — O(n · α(n))
  • Space — O(n)

Pitfalls

  • Without the edge-count check you must additionally verify a single component at the end.

Reference solution

Python

def validTree(n: int, edges) -> bool:
    if len(edges) != n - 1:
        return False
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb:
            return False
        parent[ra] = rb
    return True

Java

private static int findRoot(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

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

C++

static int findRoot(vector<int>& parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

bool validTree(int n, vector<vector<int>>& edges) {
    if ((int) edges.size() != n - 1) return false;
    vector<int> parent(n);
    for (int i = 0; i < n; i++) parent[i] = i;
    for (const auto& e : edges) {
        int a = findRoot(parent, e[0]);
        int b = findRoot(parent, e[1]);
        if (a == b) return false;
        parent[a] = b;
    }
    return true;
}

JavaScript

var validTree = function(n, edges) {
    if (edges.length !== n - 1) return false;
    const parent = [];
    for (let i = 0; i < n; i++) parent.push(i);
    const find = function(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    for (let i = 0; i < edges.length; i++) {
        const a = find(edges[i][0]);
        const b = find(edges[i][1]);
        if (a === b) return false;
        parent[a] = b;
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)