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.

A dependency network is a tree only when every node is reachable and no route loops back to an earlier node. Return true when the undirected edges form one connected, acyclic tree on n nodes. A tree must have exactly n - 1 edges as well as connectivity. Write valid_tree(n: int, edges: list) -> bool. The 5-node sample has four edges, is connected, and has no cycle, so it is a valid tree. The starter file already contains the function name, harness and print lines. Keep them and fill only the function body.

Requirements

• Reject an edge count other than n - 1.
• Check that every node is reachable.
• Reject cycles.

Constraints

• The graph is undirected and nodes are 0 to n - 1.
• Return a boolean.

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