Check if a Graph is a Tree: Three Algorithms in Python

An undirected graph is a tree if and only if it is connected and contains no cycles; for V vertices that means exactly V-1 edges.

All three properties are equivalent: any two of them imply the third. Knowing this lets you pick the fastest check for the input you have.

What Makes a Graph a Tree

According to Wikipedia’s definition of a tree in graph theory, an undirected graph G = (V, E) is a tree when all of the following hold simultaneously:

• Connected: there is a path between every pair of vertices.
• Acyclic: there are no cycles (no path from a vertex back to itself through distinct edges).
• Edge count: |E| = |V| - 1.

Because these three conditions are mutually dependent, checking any two is sufficient to confirm the third. In practice, most algorithms check the acyclic condition and the connectivity condition together, with the edge-count check as a fast pre-filter.

Two test cases used throughout this article

• Test graph A (tree): 5 nodes (0 through 4), edges 0-1, 1-2, 2-3, 3-4. Edge count = 4 = V-1. No cycles. Connected. This is a tree.
• Test graph B (not a tree): 5 nodes (0 through 4), edges 0-1, 1-2, 2-3, 3-4, 4-1. Edge count = 5, which is not equal to V-1. Contains a cycle 1-2-3-4-1. Not a tree.

Approach 1: DFS with Parent Tracking

How it works

Start a depth-first search from any node. As you visit each vertex, track its parent in the DFS tree. When you encounter an already-visited neighbour that is not the current vertex’s parent, you have found a back edge: a cycle exists and the graph is not a tree. After the DFS completes, check that all vertices were visited (connectivity check). If any vertex is unreachable, the graph is disconnected and therefore not a tree.

Python implementation

from collections import defaultdict

def is_tree_dfs(num_vertices: int, edges: list[tuple[int, int]]) -> bool:
    """Return True if the undirected graph with num_vertices nodes and
    the given edge list is a tree."""
    if num_vertices == 0:
        return True
    # Fast pre-filter: a tree must have exactly V-1 edges
    if len(edges) != num_vertices - 1:
        return False

    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    visited = [False] * num_vertices

    def dfs(node: int, parent: int) -> bool:
        visited[node] = True
        for neighbour in adj[node]:
            if not visited[neighbour]:
                if not dfs(neighbour, node):
                    return False
            elif neighbour != parent:
                return False  # back edge: cycle detected
        return True

    if not dfs(0, -1):
        return False

    # Connectivity check: all vertices must have been reached
    return all(visited)


# Test graph A: tree
edges_a = [(0, 1), (1, 2), (2, 3), (3, 4)]
print(is_tree_dfs(5, edges_a))   # True

# Test graph B: has cycle
edges_b = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 1)]
print(is_tree_dfs(5, edges_b))   # False

Manual trace on test graph A

• DFS(0, parent=-1): mark 0 visited. Visit neighbour 1.
• DFS(1, parent=0): mark 1 visited. Visit neighbour 0 (parent, skip). Visit neighbour 2.
• DFS(2, parent=1): mark 2 visited. Visit neighbour 3.
• DFS(3, parent=2): mark 3 visited. Visit neighbour 4.
• DFS(4, parent=3): mark 4 visited. Neighbour 3 is parent (skip). Return True.
• All 5 nodes visited. No back edge found. Result: True (tree).

On test graph B, the extra edge 4-1 means at node 4, neighbour 1 is already visited and is not the parent (parent is 3). Back edge detected. Result: False (not a tree).

C++ implementation

#include <vector>
#include <iostream>
using namespace std;

bool dfs(int node, int parent,
         vector<vector<int>>& adj,
         vector<bool>& visited) {
    visited[node] = true;
    for (int nb : adj[node]) {
        if (!visited[nb]) {
            if (!dfs(nb, node, adj, visited))
                return false;
        } else if (nb != parent) {
            return false;  // back edge: cycle
        }
    }
    return true;
}

bool isTree(int V, vector<pair<int,int>>& edges) {
    if ((int)edges.size() != V - 1) return false;

    vector<vector<int>> adj(V);
    for (auto& [u, v] : edges) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<bool> visited(V, false);
    if (!dfs(0, -1, adj, visited)) return false;

    for (bool v : visited)
        if (!v) return false;
    return true;
}

All vector<int>, vector<bool>, and vector<pair<int,int>> types in the C++ code above are contained in the fenced block. No angle brackets appear outside code fences.

Approach 2: Union-Find

Union-Find (disjoint-set data structure) maintains a collection of disjoint sets and supports two operations in near-constant amortised time: find (which set does this element belong to?) and union (merge two sets). For graph problems, this translates directly to cycle detection.

Process each edge one at a time. Before adding edge (u, v), check whether u and v already share a root. If they do, adding this edge would create a cycle. If they do not, merge their sets.

Pair this with the edge-count pre-filter (len(edges) == num_vertices - 1) to handle disconnected forests, which Union-Find alone would not flag as non-trees.

Python implementation

def is_tree_union_find(num_vertices: int, edges: list[tuple[int, int]]) -> bool:
    """Return True if the undirected graph is a tree using Union-Find."""
    if len(edges) != num_vertices - 1:
        return False

    parent = list(range(num_vertices))
    rank = [0] * num_vertices

    def find(x: int) -> int:
        if parent[x] != x:
            parent[x] = find(parent[x])  # path compression
        return parent[x]

    def union(x: int, y: int) -> bool:
        rx, ry = find(x), find(y)
        if rx == ry:
            return False  # cycle detected
        # Union by rank keeps the tree shallow
        if rank[rx] < rank[ry]:
            rx, ry = ry, rx
        parent[ry] = rx
        if rank[rx] == rank[ry]:
            rank[rx] += 1
        return True

    for u, v in edges:
        if not union(u, v):
            return False  # cycle found

    return True  # V-1 edges, no cycle: connected and acyclic => tree


# Test graph A: tree
print(is_tree_union_find(5, [(0,1),(1,2),(2,3),(3,4)]))   # True

# Test graph B: has cycle
print(is_tree_union_find(5, [(0,1),(1,2),(2,3),(3,4),(4,1)]))  # False

Manual trace on test graph A

Starting state: parent = [0, 1, 2, 3, 4].

• Edge (0,1): find(0)=0, find(1)=1 — different roots. Union. parent = [0, 0, 2, 3, 4].
• Edge (1,2): find(1)=0, find(2)=2 — different roots. Union. parent = [0, 0, 0, 3, 4].
• Edge (2,3): find(2)=0, find(3)=3 — different roots. Union. parent = [0, 0, 0, 0, 4].
• Edge (3,4): find(3)=0, find(4)=4 — different roots. Union. parent = [0, 0, 0, 0, 0].
• All 4 edges processed, no cycle. Result: True (tree).

On test graph B, edge (4,1) gives find(4)=0 and find(1)=0, which are the same root. Cycle detected. Result: False.

Approach 3: Edge Count and BFS Connectivity

This approach makes the two-phase structure explicit. Phase 1 is the pre-filter: if the edge count is not exactly num_vertices - 1, return False immediately. Phase 2 is a BFS (or DFS) from any node to count reachable vertices. If the count equals num_vertices, the graph is connected. Together, V-1 edges and full connectivity guarantee no cycles.

This is the most readable version and the easiest to explain in an interview.

Python implementation

from collections import defaultdict, deque

def is_tree_bfs(num_vertices: int, edges: list[tuple[int, int]]) -> bool:
    """Return True if the undirected graph is a tree using edge count + BFS."""
    if len(edges) != num_vertices - 1:
        return False

    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    visited = [False] * num_vertices
    queue = deque([0])
    visited[0] = True
    count = 1

    while queue:
        node = queue.popleft()
        for neighbour in adj[node]:
            if not visited[neighbour]:
                visited[neighbour] = True
                count += 1
                queue.append(neighbour)

    return count == num_vertices


# Test graph A: tree
print(is_tree_bfs(5, [(0,1),(1,2),(2,3),(3,4)]))    # True

# Test graph B: has cycle (edge count check fails first)
print(is_tree_bfs(5, [(0,1),(1,2),(2,3),(3,4),(4,1)]))  # False

The edge-count pre-filter means test graph B is rejected without running BFS at all, since 5 is not equal to 4.

Complexity of All Three Approaches

All three approaches have the same asymptotic profile, which matches the space complexity analysis for adjacency-list traversals.

Approach	Time complexity	Auxiliary space	Notes
DFS with parent tracking	O(V+E)	O(V)	Recursion stack adds O(V) depth
Union-Find	O(E · α(V))	O(V)	α is inverse Ackermann — near O(1) per edge
Edge count + BFS	O(V+E)	O(V)	Simplest to explain in an interview

For a connected graph where E = V-1, all three reduce to O(V). The Union-Find version is marginally faster in practice due to lower constant factors, but the difference is imperceptible on the input sizes seen in placement coding rounds.

Graph traversal problems (including this one) are standard fare in technical screening rounds. For interview preparation context on what companies ask, see PayPal interview questions and process.

For a deeper look at array-based traversal patterns that share structural similarities with graph problems, the article on finding all symmetric pairs in an array covers nested-loop and hash-map approaches at the same O(n) level.

Union-Find and DFS back-edge detection appear in production AI code more often than most placement tutorials mention. Knowledge graph construction, dependency resolution in ML pipelines, and cluster detection in recommendation systems all reduce to the same primitives covered here. TinkerLLM builds these connections hands-on; the entry plan starts at ₹299.