Graph Valid Tree

Graph Valid Tree is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Union-Find (Disjoint Set Union - DSU) subpattern.

Problem statement

You are given an integer n, representing the number of nodes labeled from 0 to n - 1, and a list of undirected edges edges, where each edge is represented as a pair [a, b] indicating a connection between nodes a and b.

A graph is considered a valid tree if it is connected (there is a path between any two nodes) and acyclic (contains no cycles).

Return true if the given edges form a valid tree with n nodes, and false otherwise.

Topics and companies

Topics: Depth-First Search, Breadth-First Search, Union Find, Graph.

Reported in interviews at Amazon, Qualtrics, Microsoft.

How to practise Graph Valid Tree on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n + m), where n is the number of nodes and m is the number of edges. Building the adjacency list takes O(m), and the BFS traversal visits each node and edge at most once. time and O(n + m), for the adjacency list (O(n + m)), the visited array (O(n)), and the BFS queue (up to O(n)). space.

Open Graph Valid Tree in the code editor, or read the Graph Valid Tree editorial for a worked solution with its approach and complexity analysis.

Where Graph Valid Tree sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Union-Find (Disjoint Set Union - DSU) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Graph Valid Tree

Other problems that use the same Union-Find (Disjoint Set Union - DSU) and Graph Traversal Patterns (DFS & BFS) techniques:

• Accounts Merge — Medium, same subpattern
• Largest Component Size by Common Factor — Hard, same subpattern
• Most Stones Removed with Same Row or Column — Medium, same subpattern
• Number of Connected Components in an Undirected Graph — Medium, same subpattern
• Number of Islands II — Hard, same subpattern
• Redundant Connection — Medium, same subpattern