v9.1.1
Menu

Graph Valid Tree

mediumPROGraphs & Shortest PathsUber DSA

Given n nodes (0 to n-1) and a list of undirected edges, check if these edges form a valid tree (connected, no cycles).

Implement valid_tree(n, edges), where n is an integer and edges is a list of [u, v] pairs (an empty list when there are no edges). Return True if the edges form a valid tree, otherwise False.

Example

Input
5
0:1,0:2,0:3,1:4
Output
True
Reasoning
  • n is 5, so the nodes are labelled 0 to 4. edges lists 4 undirected connections: (0,1),(0,2),(0,3),(1,4)(0,1), (0,2), (0,3), (1,4). Each pair links its two nodes in both directions.
  • A tree on nn nodes always has exactly n−1n-1 edges: fewer leaves some node cut off, more forces a cycle. Here n−1=5−1=4n - 1 = 5 - 1 = 4, and there are exactly 4 edges, so the count is right.
  • The count alone is not enough; the edges must also reach every node. Node 0 touches nodes 1, 2 and 3 directly, and node 4 hangs off node 1. All 5 nodes sit in one connected piece.
  • Four edges joining five nodes into a single piece leave no spare edge, so no cycle can exist. The answer is True.
  • Notice how the other cases differ: 5 edges on 5 nodes, (0,1),(1,2),(2,3),(1,3),(1,4)(0,1), (1,2), (2,3), (1,3), (1,4), contain the loop 1→2→3→11 \to 2 \to 3 \to 1 and give False, while a single node with no edges is a valid tree, since 1−1=01 - 1 = 0.

Constraints

  • 1 <= n <= 2000
  • 0 <= edges.length <= 5000

Learn this in

More from Uber DSA

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Test results

Sign in to run your code against the test cases.