261. Graph Valid TreeMedium

Graph Valid Tree

MediumGraphDepth-First SearchBreadth-First SearchUnion Find·AmazonGoogle

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [a_i, b_i] indicates that there is an undirected edge between nodes a_i and b_i in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

Example 1:

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

Output:true

Example 2:

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

Output:false

Hints

Hint 1Properties of a Tree.▼

A valid tree must have precisely n - 1 edges and it must be fully connected (all nodes are reachable from starting point).

Hint 2How to detect cycles using DFS?▼

When traversing from node to a neighbor, if the neighbor is already visited AND it is not the parent node that brought you here, you've found a cycle!

Optimal Approach — Depth First Search (DFS)

O(N + E) Time

🔍

Traverse Graph using DFS & Count Nodes visited

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

We can utilize depth-first search to traverse our given graph. While exploring, we track visited nodes and the parent of the current node.

1Quick check: A tree with n nodes must have exactly n - 1 edges.
2Build an adjacency list representation of the graph.
3Run DFS from node 0. Passing down its parent to avoid traversing backwards.
4If a visited node is encountered that is not the parent, a cycle exists. Return false.
5After DFS finishes, verify len(visited) == n to verify there are no disconnected components.

DFS Graph Traversal

📋 Call Stack

— empty —

✓ Visited Set

∅

🔗 Adjacency List parent → [children]

—

READY—

Press ▶ or step forward to begin.

✓

—

N Nodes

Edges (JSON)

Executing Code

def validTree(n, edges):

    if len(edges) != n - 1: return False

    adj = [[] for _ in range(n)]

    for u, v in edges: adj[u].append(v); adj[v].append(u)

    visited = set()

    def dfs(node, parent):

        if node in visited: return False

        visited.add(node)

        for nxt in adj[node]:

            if nxt != parent:

                if not dfs(nxt, node): return False

        return True

    return dfs(0, -1) and len(visited) == n

Alternative Approach — Breadth First Search (BFS)

O(N + E) Time

🌊

Layer-by-Layer Traversal using Queue

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

Similar to DFS, we can also use **Breadth First Search (BFS)** to identify a valid tree. Instead of going as deep as possible, BFS explores node connections layer-by-layer.

BFS Graph Traversal

🔄 Queue

— empty —

✓ Visited Set

∅

🔗 Adjacency List parent → [children]

—

READY—

Press ▶ or step forward to begin.

✓

—

N Nodes

Edges (JSON)

Executing Code

from collections import deque

def validTreeBFS(n, edges):

    if len(edges) != n - 1: return False

    adj = [[] for _ in range(n)]

    for u, v in edges: adj[u].append(v); adj[v].append(u)

    queue = deque([0])

    visited = set([0])

    while queue:

        node = queue.popleft()

        for nb in adj[node]:

            if nb not in visited:

                visited.add(nb)

                queue.append(nb)

    return len(visited) == n

Discussion

…

Loading comments…

LeetMotion

Graph Valid Tree

MediumGraphDepth-First SearchBreadth-First SearchUnion Find·AmazonGoogle

Return true if the edges of the given graph make up a valid tree, and false otherwise.

Example 1:

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

Output:true

Example 2:

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

Output:false

Hints

Hint 1Properties of a Tree.▼

A valid tree must have precisely n - 1 edges and it must be fully connected (all nodes are reachable from starting point).

Hint 2How to detect cycles using DFS?▼

When traversing from node to a neighbor, if the neighbor is already visited AND it is not the parent node that brought you here, you've found a cycle!

Optimal Approach — Depth First Search (DFS)

O(N + E) Time

🔍

Traverse Graph using DFS & Count Nodes visited

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

We can utilize depth-first search to traverse our given graph. While exploring, we track visited nodes and the parent of the current node.

1Quick check: A tree with n nodes must have exactly n - 1 edges.
2Build an adjacency list representation of the graph.
3Run DFS from node 0. Passing down its parent to avoid traversing backwards.
4If a visited node is encountered that is not the parent, a cycle exists. Return false.
5After DFS finishes, verify len(visited) == n to verify there are no disconnected components.

DFS Graph Traversal

📋 Call Stack

— empty —

✓ Visited Set

∅

🔗 Adjacency List parent → [children]

—

READY—

Press ▶ or step forward to begin.

✓

—

N Nodes

Edges (JSON)

Executing Code

def validTree(n, edges):

    if len(edges) != n - 1: return False

    adj = [[] for _ in range(n)]

    for u, v in edges: adj[u].append(v); adj[v].append(u)

    visited = set()

    def dfs(node, parent):

        if node in visited: return False

        visited.add(node)

        for nxt in adj[node]:

            if nxt != parent:

                if not dfs(nxt, node): return False

        return True

    return dfs(0, -1) and len(visited) == n

Alternative Approach — Breadth First Search (BFS)

O(N + E) Time

🌊

Layer-by-Layer Traversal using Queue

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

Similar to DFS, we can also use **Breadth First Search (BFS)** to identify a valid tree. Instead of going as deep as possible, BFS explores node connections layer-by-layer.

BFS Graph Traversal

🔄 Queue

— empty —

✓ Visited Set

∅

🔗 Adjacency List parent → [children]

—

READY—

Press ▶ or step forward to begin.

✓

—

N Nodes

Edges (JSON)

Executing Code

from collections import deque

def validTreeBFS(n, edges):

    if len(edges) != n - 1: return False

    adj = [[] for _ in range(n)]

    for u, v in edges: adj[u].append(v); adj[v].append(u)

    queue = deque([0])

    visited = set([0])

    while queue:

        node = queue.popleft()

        for nb in adj[node]:

            if nb not in visited:

                visited.add(nb)

                queue.append(nb)

    return len(visited) == n