Interview Notes Search

Depth-First Search

Graph Valid Tree

medium

DESCRIPTION (inspired by Lintcode.com)

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

Every node from 0 to n - 1 is part of the graph, even if it does not appear in any edge.

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]]

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:

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

graph valid tree

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.

build adjacency list

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.

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

iterate over neighbors

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

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

graph valid tree

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.