We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Graph Valid Tree

Number: 261

Difficulty: Medium

Paid? Yes

Companies: Google, LinkedIn, Amazon, Microsoft, Salesforce, Snowflake, Meta, TikTok, Zenefits

Problem Description

Given n nodes labeled from 0 to n - 1 and an edge list representing an undirected graph, determine if these edges form a valid tree. A valid tree satisfies both connectivity (all nodes are connected) and acyclicity (no cycles exist). Additionally, when there are n nodes, a tree must have exactly n - 1 edges.

Key Insights

  • A tree must be acyclic and connected.
  • For n nodes, a valid tree must have exactly n - 1 edges.
  • A DFS/BFS traversal can check connectivity and simultaneously detect cycles.
  • The Union-Find (disjoint set) approach provides an alternative for cycle detection and connectivity verification.

Space and Time Complexity

Time Complexity: O(n + e), where e is the number of edges
Space Complexity: O(n + e) for storing the graph and traversal/union-find structures

Solution

We can solve the problem using either a DFS/BFS approach or a Union-Find algorithm. For the DFS/BFS method, we first check if the number of edges is exactly n - 1. If not, it cannot be a tree. Then, we build an adjacency list for the graph and perform a DFS starting from node 0 while keeping track of visited nodes and parent information to avoid false-positive cycle detections. If during DFS we encounter a node that has been visited (and is not the parent), then a cycle exists. Finally, if all nodes are reached from node 0 and no cycle is found, the graph is a valid tree.

Using Union-Find, we iterate over each edge and try to union the two nodes. If they already share the same parent (i.e., are in the same set), a cycle exists. After processing all edges, we confirm that exactly one connected component exists.

Code Solutions

# Python solution with DFS

def validTree(n, edges):
    # If the number of edges is not exactly n - 1, it cannot be a tree
    if len(edges) != n - 1:
        return False

    # Build the graph as an adjacency list
    graph = {i: [] for i in range(n)}
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    
    visited = set()

    # DFS helper function that accepts current node and its parent node
    def dfs(node, parent):
        # Add the current node to visited
        visited.add(node)
        # Traverse all the neighboring nodes
        for neighbor in graph[node]:
            # Skip the neighbor if it is the parent to avoid trivial cycle detection
            if neighbor == parent:
                continue
            # If neighbor is already visited, a cycle is detected
            if neighbor in visited:
                return False
            # Recurse deeper; if cycle is found in recursion, propagate False upward
            if not dfs(neighbor, node):
                return False
        return True

    # Start DFS from node 0, with parent set to -1 (non-existent)
    if not dfs(0, -1):
        return False

    # Check if all nodes were visited (i.e., the graph is connected)
    return len(visited) == n

# Example usage:
print(validTree(5, [[0, 1], [0, 2], [0, 3], [1, 4]]))  # Expected output: True
print(validTree(5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]))  # Expected output: False
← Back to All Questions