Coding

Graph Valid Tree

Asked at

Amazon

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The 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.

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Output: true Explanation: The graph consists of 5 nodes labeled from 0 to 4 and has 4 edges. A valid tree must have exactly n-1 edges, which in this case is 4, so the count is correct. Additionally, there are no cycles because every new edge connects a previously disconnected node. The graph is also fully connected, meaning all nodes can be reached from any other node. Since all conditions of a tree are satisfied, the given graph forms a valid tree.

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]] Output: false Explanation: The graph consists of 5 nodes and 5 edges. A valid tree must have exactly n-1 edges, but here there are 5 edges instead of 4, which is already a problem. Additionally, the edge [1,3] forms a cycle because there is already a path from 1 to 3 through 1-2-3. Even though the graph is connected, the presence of a cycle means it does not satisfy the conditions of a tree. Therefore, the given graph is not a valid tree.

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

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.

cpp

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        // Your code goes here
    }
};

java

class Solution {
    public boolean validTree(int n, int[][] edges) {
        // Your code goes here
    }
}

python

class Solution(object):
    def validTree(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        # Your code goes here

javascript

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {boolean}
 */
var validTree = function(n, edges) {
    // Your code goes here
};

csharp

public class Solution
{
    public bool ValidTree(int n, List<Tuple<int, int>> edges)
    {
        // Your code goes here
    }
}

func validTree(n int, edges [][]int) bool {

}

Stuck? Show a way to structure it+

01Reject immediately unless edge count is n-1
02Build adjacency lists or initialize DSU
03Traverse from one node or union edges detecting cycles
04Verify every node belongs to the same component

Reference answer

Start by restating the input contract for Graph Valid Tree and testing the smallest boundary case before choosing the algorithm. An undirected graph on n nodes is a tree exactly when it has n-1 edges and is connected. Check the edge count, then run DFS/BFS from one node and ensure all n nodes are visited. Union-find is an equally good alternative for streaming edges. Explain the invariant while coding, then show how each update preserves it. The edge check plus traversal costs O(V + E) time and O(V + E) space for the adjacency list and visited set. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

How do you detect the first cycle with DSU?
Tests: follow-up reasoning
How would this work for directed graphs?
Tests: follow-up reasoning

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question