TheAlgorithms/Java · error · IllegalArgumentException

Tree must have exactly n-1 edges

Error message

Tree must have exactly n-1 edges

What it means

Thrown by CentroidDecomposition.buildFromEdges when the number of edges is not exactly n-1. A valid tree on n nodes has precisely n-1 edges; any other count indicates a malformed tree (cycle, disconnected, or extra edges). The IllegalArgumentException enforces this invariant before constructing the adjacency list.

Source

Thrown at src/main/java/com/thealgorithms/datastructures/trees/CentroidDecomposition.java:192

    }

    /**
     * Creates a centroid tree from an edge list.
     *
     * @param n number of nodes (0-indexed: 0 to n-1)
     * @param edges list of edges where each edge is [u, v]
     * @return CentroidTree object
     * @throws IllegalArgumentException if n <= 0 or edges is invalid
     */
    public static CentroidTree buildFromEdges(int n, int[][] edges) {
        if (n <= 0) {
            throw new IllegalArgumentException("Number of nodes must be positive");
        }
        if (edges == null) {
            throw new IllegalArgumentException("Edges cannot be null");
        }
        if (edges.length != n - 1) {
            throw new IllegalArgumentException("Tree must have exactly n-1 edges");
        }

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            if (edge.length != 2) {
                throw new IllegalArgumentException("Each edge must have exactly 2 nodes");
            }
            int u = edge[0];
            int v = edge[1];

            if (u < 0 || u >= n || v < 0 || v >= n) {
                throw new IllegalArgumentException("Invalid node in edge: [" + u + ", " + v + "]");
            }

View on GitHub (pinned to fdfb9a395b)

Solutions

1. Verify the input is a valid tree: exactly n-1 unique edges connecting all n nodes with no cycles.
2. Ensure n matches the true vertex count of the edge list.
3. Deduplicate undirected edges (treat [u,v] and [v,u] as one) before counting.
4. Run a connectivity/cycle check before calling buildFromEdges.

Example fix

// before
CentroidTree ct = CentroidDecomposition.buildFromEdges(n, edges);
// after
if (edges.length != n - 1) {
    throw new IllegalArgumentException(
        "Expected " + (n - 1) + " edges for " + n + " nodes, got " + edges.length);
}
CentroidTree ct = CentroidDecomposition.buildFromEdges(n, edges);

if (edges.length == n - 1) {
    CentroidTree ct = CentroidDecomposition.buildFromEdges(n, edges);
} else {
    throw new IllegalArgumentException("tree must have n-1 edges");
}

When it happens

Trigger: Passing n-2 edges (disconnected forest). Passing n edges (a cycle). Passing edges with duplicates or self-loops inflating the count. Mismatch between n and the actual vertex set used to build edges.

Common situations: Input data that is not actually a tree (general graph mistaken for a tree). Off-by-one in computing n relative to the edges. Merging edge lists that introduce duplicates. Self-loops or duplicate undirected edges counted twice.

Related errors

• Invalid node: {}
• Number of nodes must be positive
• Each edge must have exactly 2 nodes
• Invalid node in edge: [{}, {}]
• Tree cannot be empty or null

AI-assisted analysis of TheAlgorithms/Java@fdfb9a395b (2026-08-13). Data as JSON: /api/errors/315fdda594576a2f. Report an issue: GitHub.