Skip to content
LakeBench
ProblemsCommunityPricing
Sign inStart practicing

Graph Valid Tree

Python data engineering interview problem. Difficulty: advanced. Pattern: Graphs. About 18 minutes. Part of the Pro drill bank.

Check whether edges form a valid tree on n nodes. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.

Implement valid_tree(n: int, edges: list) -> bool. A valid tree has exactly n-1 edges and is fully connected with no cycles.

Constraints

  • Nodes are 0..n-1.
  • Undirected edges.

Examples

Input: valid_tree(5, [[0, 1], [0, 2], [0, 3], [1, 4]]) Output: True Connected acyclic with 4 edges.

Topics: lakebench, python, tree, union-find.

More Python interview questions · All interview problems · Learn data engineering

advanced

Graph Valid Tree

Interview-style drill: Check whether edges form a valid tree on n nodes.

Implement `valid_tree(n: int, edges: list) -> bool`. A valid tree has exactly n-1 edges and is fully connected with no cycles. Example: `5, [[0, 1], [0, 2], [0, 3], [1, 4]]` → `True`. Keep the harness.