TheAlgorithms/Java · error · IllegalArgumentException

Invalid root: {root}

Error message

Invalid root: {root}

What it means

Thrown by TreeMatching.getMaxMatching(int root, int parent) when root is outside [0, graph.size()). The DP table dp[root][0/1] is indexed by root, so an out-of-range index would throw ArrayIndexOutOfBoundsException; the library validates explicitly. Message: 'Invalid root: <root>'.

Source

Thrown at src/main/java/com/thealgorithms/dynamicprogramming/TreeMatching.java:42

     *
     * @param graph The graph that represents the tree and is used for the matching algorithm.
     */
    public TreeMatching(UndirectedAdjacencyListGraph graph) {
        this.graph = graph;
        this.dp = new int[graph.size()][2];
    }

    /**
     * Calculates the maximum weighted matching for the tree, starting from the given root node.
     *
     * @param root The index of the root node of the tree.
     * @param parent The index of the parent node (used for recursion).
     * @return The maximum weighted matching for the tree, starting from the root node.
     *
     */
    public int getMaxMatching(int root, int parent) {
        if (root < 0 || root >= graph.size()) {
            throw new IllegalArgumentException("Invalid root: " + root);
        }
        maxMatching(root, parent);
        return Math.max(dp[root][0], dp[root][1]);
    }

    /**
     * Recursively computes the maximum weighted matching for a node, assuming that the node
     * can either be included or excluded from the matching.
     *
     * @param node The index of the current node for which the matching is calculated.
     * @param parent The index of the parent node (to avoid revisiting the parent node during recursion).
     */
    private void maxMatching(int node, int parent) {
        dp[node][0] = 0;
        dp[node][1] = 0;

        int sumWithoutEdge = 0;
        for (int adjNode : graph.getNeighbors(node)) {

View on GitHub (pinned to fdfb9a395b)

Solutions

1. Pass a valid root index in [0, graph.size()); use -1 only for the parent argument (which is not bounds-checked), not for root.
2. Convert external vertex ids to internal 0-based indices before calling.
3. Validate root against graph.size() at the call site.

Example fix

// before
int m = matcher.getMaxMatching(-1, -1); // wrong: -1 root

// after
int m = matcher.getMaxMatching(0, -1); // root 0, no parent

if (root < 0 || root >= graph.size()) {
    throw new IllegalArgumentException("root out of range: " + root);
}
matcher.getMaxMatching(root, parent);

When it happens

Trigger: Passing root = -1 (common sentinel for 'no parent'); root >= number of vertices; root computed from a vertex id that is 1-based while the graph is 0-based.

Common situations: Calling getMaxMatching on a tree where the root's parent is encoded as -1 and the root itself was passed -1 by mistake; mixing 1-based external ids with 0-based internal indices.

Related errors

• Neighbor index out of bounds: {v}
• Number of vertices must be positive
• Edges list must not be null or empty
• Edge vertex out of range
• Source vertex is out of bounds.

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