Search
⌘K
Depth-First Search

Graph Valid Tree

medium
DESCRIPTION (inspired by Lintcode.com)

You are given an integer n and a list of undirected edges where each entry in the list is a pair of integers representing an edge between nodes 0 and n - 1. You have to write a function to check whether these edges make up a valid tree.

There will be no duplicate edges in the edges list. (i.e. [0, 1] and [1, 0] will not appear together in the list).

Input:

n = 4 
edges = [[0, 1], [2, 3]]
3210

Output:

false # the graph is not connected.

Explanation

In order for a graph to be a valid tree, it must satisfy the following conditions:
  1. The graph must contain no cycles.
  2. There should be a single connected component - if we start from any node, we should be able to reach all other nodes.
We can use a depth-first search to check for these conditions. We'll start by converting the list of edges into an adjacency list. This allows us to easily find the neighbors of any node, which is required by the depth-first search algorithm.
We'll walkthrough how this solution determines that a graph with a cycle is not a valid tree when n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], which forms the following graph:
43210
Visualization
def validTree(n, edges):
  adj_list = [[] for _ in range(n)]
  for u, v in edges:
    adj_list[u].append(v)
    adj_list[v].append(u)
  # Use DFS to check if the graph is a valid tree
  visited = [False] * n
  if hasCycle(adj_list, 0, visited, -1):
    return False
  return all(visited)
def hasCycle(adj_list, node, visited, parent):
  visited[node] = True
  for neighbor in adj_list[node]:
    if visited[neighbor] and parent != neighbor:
      return True
    elif not visited[neighbor] and \
        hasCycle(adj_list, neighbor, visited, node):
      return True
  return False
[0, 1][1, 2][2, 3][1, 3][1, 4]

graph valid tree

0 / 6

Building the adjacency list.
Next, we use a recursive function hasCycle to check for cycles in the graph. Each call to hasCycle returns true if there is a cycle connected to the input node. The function first marks the current node as visited, then recursively visits all its neighbors using depth-first search, checking for cycles. To keep track of the nodes we've visited already, we use a boolean array visited.
Visualization
def validTree(n, edges):
  adj_list = [[] for _ in range(n)]
  for u, v in edges:
    adj_list[u].append(v)
    adj_list[v].append(u)
  # Use DFS to check if the graph is a valid tree
  visited = [False] * n
  if hasCycle(adj_list, 0, visited, -1):
    return False
  return all(visited)
def hasCycle(adj_list, node, visited, parent):
  visited[node] = True
  for neighbor in adj_list[node]:
    if visited[neighbor] and parent != neighbor:
      return True
    elif not visited[neighbor] and \
        hasCycle(adj_list, neighbor, visited, node):
      return True
  return False
[0, 1][1, 2][2, 3][1, 3][1, 4][u, v]node0:11:02342:133:214:1

build adjacency list

0 / 5

Recursively calling `hasCycle`

Detecting a Cycle

If at any point during our search, we encounter a node that we've already visited and is not the parent of the current node, then we've found a cycle. We return true to indicate that the graph is not a valid tree, which causes the depth-first search to terminate early, until the main function returns false.
Visualization
def validTree(n, edges):
  adj_list = [[] for _ in range(n)]
  for u, v in edges:
    adj_list[u].append(v)
    adj_list[v].append(u)
  # Use DFS to check if the graph is a valid tree
  visited = [False] * n
  if hasCycle(adj_list, 0, visited, -1):
    return False
  return all(visited)
def hasCycle(adj_list, node, visited, parent):
  visited[node] = True
  for neighbor in adj_list[node]:
    if visited[neighbor] and parent != neighbor:
      return True
    elif not visited[neighbor] and \
        hasCycle(adj_list, neighbor, visited, node):
      return True
  return False
def hasCycle(adj_list, node, visited, parent):
  visited[node] = True
  for neighbor in adj_list[node]:
    if visited[neighbor] and parent != neighbor:
      return True
    elif not visited[neighbor] and \
        hasCycle(adj_list, neighbor, visited, node):
      return True
  return False
def hasCycle(adj_list, node, visited, parent):
  visited[node] = True
  for neighbor in adj_list[node]:
    if visited[neighbor] and parent != neighbor:
      return True
    elif not visited[neighbor] and \
        hasCycle(adj_list, neighbor, visited, node):
      return True
  return False
def hasCycle(adj_list, node, visited, parent):
  visited[node] = True
  for neighbor in adj_list[node]:
    if visited[neighbor] and parent != neighbor:
      return True
    elif not visited[neighbor] and \
        hasCycle(adj_list, neighbor, visited, node):
      return True
  return False
def hasCycle(adj_list, node, visited, parent):
  visited[node] = True
  for neighbor in adj_list[node]:
    if visited[neighbor] and parent != neighbor:
      return True
    elif not visited[neighbor] and \
        hasCycle(adj_list, neighbor, visited, node):
      return True
  return False
[0, 1][1, 2][2, 3][1, 3][1, 4][u, v]node0:11:02342:133:214:1nodeparentneighborvisitedTTTTFnode: 3parent: 2

iterate over neighbors

0 / 5

The node `1` has already been visited and is not the parent of the current node `3`.
If no cycle is found, then we have to make sure there is a single connected component. We do this by checking if all nodes have been visited. If so, the graph is a valid tree and we return true. If not, then the graph is not a valid tree and we return false.

Animated Solution

|
list of nodes [start, end]
|
integer
Try these examples:
Visualization
def validTree(n, edges):
  adj_list = [[] for _ in range(n)]
  for u, v in edges:
    adj_list[u].append(v)
    adj_list[v].append(u)
  # Use DFS to check if the graph is a valid tree
  visited = [False] * n
  if hasCycle(adj_list, 0, visited, -1):
    return False
  return all(visited)
def hasCycle(adj_list, node, visited, parent):
  visited[node] = True
  for neighbor in adj_list[node]:
    if visited[neighbor] and parent != neighbor:
      return True
    elif not visited[neighbor] and \
        hasCycle(adj_list, neighbor, visited, node):
      return True
  return False
[0, 1][1, 2][2, 3][1, 3][1, 4]

graph valid tree

0 / 27

Complexity Analysis

For this problem, let n be the number of nodes and e be the number of edges.
Test Your Knowledge

Login to take the complexity quiz and track your progress

Complexity Analysis

Time Complexity: O(n + e) Building the adjacency list takes O(e) time, and the DFS visits each node once and traverses each edge once, taking O(n + e) time.

Space Complexity: O(n + e) The adjacency list stores all edges, taking O(n + e) space. The visited array takes O(n) space, and the recursion stack can grow up to O(n) deep in the worst case.

Mark as read

Next: Matrices

Your account is free and you can post anonymously if you choose.

Unlock Premium Coding Content

Interactive algorithm visualizations
Guided Practice
Recent interview questions
Learn More
Reading Progress

On This Page

Explanation

Depth-First Search

Detecting a Cycle

Animated Solution

Complexity Analysis

Questions
Meta SWE Interview QuestionsAmazon SWE Interview QuestionsGoogle SWE Interview QuestionsOpenAI SWE Interview QuestionsEngineering Manager (EM) Interview Questions
Learn
Learn System DesignLearn DSALearn BehavioralLearn ML System DesignLearn Low Level DesignGuided Practice
Links
FAQPricingGift Mock InterviewsGift PremiumBecome a CoachOur CoachesHello Interview Premium
Legal
Terms and ConditionsPrivacy PolicySecurity
Contact
About UsProduct Support

7511 Greenwood Ave North Unit #4238 Seattle WA 98103

© 2026 Optick Labs Inc. All rights reserved.