Given n nodes labeled 0 to n-1 and a list of undirected edges, determine if these edges form a valid tree.
A valid tree has two properties: 1. It is fully connected (all nodes are reachable from any node). 2. It has no cycles.
For example:
n = 5, edges = [[0,1], [0,2], [0,3], [1,4]] -> Valid tree n = 5, edges = [[0,1], [1,2], [2,3], [1,3], [1,4]] -> Not a valid tree (has a cycle: 1-2-3-1)
Is there a quick check you can do before even traversing the graph?
Explain your approach and analyze the time and space complexity.
How to approach it
- Hint 1
A tree with n nodes has exactly n-1 edges. If the edge count is not n-1, it is definitely not a tree.
- Hint 2
With exactly n-1 edges, you still need to verify connectivity (no disconnected components).
- Hint 3
Use BFS/DFS from any node and check if all n nodes are visited. With n-1 edges and full connectivity, there can be no cycles.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.