Graph Valid Tree

Patrick Leaton

Published: July 5, 2021, 10:29 p.m.

Problem Description

Given n nodes labeled from 0 to n-1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

Example 1:

Input: n = 5, and edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true

Example 2:

Input: n = 5, and edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Output: false

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0,1] is the same as [1,0] and thus will not appear together in edges.

The description was taken from https://leetcode.com/problems/graph-valid-tree/solution/.

Problem Solution

#DFS

#O(N+E) Time, O(N+E) Space

class Solution:

def validTree(self, n: int, edges: List[List[int]]) -> bool:

if len(edges) != n - 1:

return False

adjacency, seen = {}, {}

for node in range(0,n):

adjacency[node] = []

seen[node] = False

for node, neighbor in edges:

adjacency[node].append(neighbor)

adjacency[neighbor].append(node)

def dfs(node:int) -> None:

if seen[node]:

return

seen[node] = True

for neighbor in adjacency[node]:

if not seen[neighbor]:

dfs(neighbor)

dfs(0)

for node in seen:

if not seen[node]:

return False

return True

#BFS

#O(N+E) Time, O(N+E) Space

class Solution:

def validTree(self, n: int, edges: List[List[int]]) -> bool:

if len(edges) != n - 1:

return False

adjacency, seen = {}, {}

for node in range(0,n):

adjacency[node] = []

seen[node] = False

for node, neighbor in edges:

adjacency[node].append(neighbor)

adjacency[neighbor].append(node)

def bfs(node) -> None:

queue = collections.deque([node])

while queue:

node = queue.popleft()

seen[node] = True

for neighbor in adjacency[node]:

if not seen[neighbor]:

seen[neighbor] = True

queue.append(neighbor)

bfs(0)

for node in seen:

if not seen[node]:

return False

return True

Problem Explanation

The qualification of a valid tree is there needs to be n-1 edges and each node needs to be connected.

If we had to graph a tree of three nodes, it would have one parent node and two child nodes, which would be two edges. If we had two edges, one of the nodes wouldn't be connected. If we had four nodes, then there would be a cycle in the tree, with perhaps one edge going from one child node to the other.

To see if we have a valid tree, we can first ensure the tree has n-1 edges, and that each node is connected using a Breadth-First Search or a Depth-First Search. If both those cases are valid, we have a valid tree.

Recursive Depth-First Search

Let's check that we have the right number of edges before doing anything else.

If not, the given tree is invalid.

if len(edges) != n - 1:

return False

We will start by initializing our adjacency list that maps each neighbor to each node so that we can graph a tree without physically instantiating nodes using the edges input, and also initializing our seen dictionary that keeps track of whether we have visited each specific node.

adjacency, seen = {}, {}

Once we have initialized the adjacency list and seen, we will go through each node, place it in the adjacency list with an initially empty list of neighbors, and mark it as false within seen, since we have not seen it yet within a search.

for node in range(0,n):

adjacency[node] = []

seen[node] = False

Since this is an undirected graph, the edge between each node and each neighbor goes to and from each other.

To signify this, we will go through the edges input and map each node to its neighbor, then each neighbor to the node, so that it is a two-way edge, undirected edge.

for node, neighbor in edges:

adjacency[node].append(neighbor)

adjacency[neighbor].append(node)

Next, we will build our recursive, dfs function.

The function will do a generic DFS, it will take the node that was passed to it check if it has been seen before, mark it as seen if not, then recurse any unseen neighbors of the node to do the same thing.

def dfs(node:int) -> None:

if seen[node]:

return

seen[node] = True

for neighbor in adjacency[node]:

if not seen[neighbor]:

dfs(neighbor)

We can then make our initial node, zero, to the DFS function.

dfs(0)

Once the DFS is over, we will iterate through each node in the seen dictionary and see if any have been unseen. If they have, then they were disconnected from the rest of the tree so we will return false.

for node in seen:

if not seen[node]:

return False

Otherwise, we will return True.

return True

Iterative Breadth-First Search

The only difference between the BFS and DFS version, basically the only difference in general, is a BFS uses a queue and a DFS uses a stack. The BFS will traverse each component level by level instead of the previously used DFS that will traverse it depth by depth.

All we need to do here is swap the recursive, dfs function for an iterative, bfs function.

The function will take a node and push it into a queue.

def bfs(node) -> None:

queue = collections.deque([node])

While the queue still has nodes that we need to visit, we will continue to pop a node, visit it, visit its unseen neighbors, then push its neighbors on the queue to repeat the process.

while queue:

node = queue.popleft()

seen[node] = True

for neighbor in adjacency[node]:

if not seen[neighbor]:

seen[neighbor] = True

queue.append(neighbor)