DSA interview question

Graph Basics: Is This Undirected Graph a Tree?

Easy · Data structures · Topics: graph, theory

The problem

A network team is designing a cabling plan for n offices, listed as undirected links between office numbers. The plan must be a tree: every office reachable from every other, and no redundant loops. This introduces the core graph vocabulary: vertices, edges, adjacency lists, connectivity and cycles. One quick fact does most of the work. A graph with n vertices is a tree exactly when it has n − 1 edges and is connected. So count the edges, then run a BFS from vertex 0 and check that it reaches everyone.

Example: n = 5, edges [[0,1], [0,2], [0,3], [1,4]] → true.

Function signature

bool isTree(int n, const vector<pair<int, int>>& edges);  // vertices 0..n-1, n >= 1

Test cases

Input `(n, edges)`	Output	Explanation
`(5, [[0,1],[0,2],[0,3],[1,4]])`	`true`	4 edges, connected
`(5, [[0,1],[1,2],[2,3],[1,3],[1,4]])`	`false`	5 edges: the cycle 1-2-3
`(4, [[0,1],[2,3]])`	`false`	Two pieces
`(1, [])`	`true`	A single vertex
`(2, [])`	`false`	Disconnected

(Confirm: edges are undirected; self-loops or repeated edges make it not a tree.)

How interviewers phrase it

"Given n nodes and a list of undirected edges, check whether these edges make up a valid tree" (LeetCode 261 "Graph Valid Tree"), often as the first graph question.

Clarifying questions to ask

Directed or undirected? (Undirected.)
Are vertices numbered 0 to n − 1? (Yes.)
Can there be self-loops or repeated edges? (Possibly, and they can't appear in a tree.)

Follow-ups to expect

"Basic terms?"
"How do you store it?"
"Why n − 1 edges plus connected?"
"Alternative with DSU?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview