D
DevExCode

LeetCode 261: Graph Valid Tree Solution

Master LeetCode problem 261 (Graph Valid Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To determine if a given graph is a valid tree, we need to check two conditions:

  1. The graph is fully connected (no isolated nodes).
  2. The graph has no cycles.

We can solve this problem using a depth-first search (DFS) algorithm. We will start the DFS traversal from any node and visit all its neighbors. While visiting each neighbor, we will mark the current node as visited. If we encounter a visited node, it means there is a cycle in the graph. Additionally, we will keep track of the number of connected components in the graph. If there is more than one connected component, the graph is not a valid tree.

: :

Solution Code

class Solution {
    public boolean validTree(int n, int[][] edges) {
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            adjList.get(edge[0]).add(edge[1]);
            adjList.get(edge[1]).add(edge[0]);
        }

        boolean[] visited = new boolean[n];
        if (hasCycle(-1, 0, visited, adjList)) {
            return false;
        }

        for (boolean v : visited) {
            if (!v) {
                return false;
            }
        }

        return true;
    }

    private boolean hasCycle(int parent, int node, boolean[] visited, List<List<Integer>> adjList) {
        visited[node] = true;

        for (int neighbor : adjList.get(node)) {
            if (!visited[neighbor]) {
                if (hasCycle(node, neighbor, visited, adjList)) {
                    return true;
                }
            } else if (neighbor != parent) {
                return true;
            }
        }

        return false;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 261 (Graph Valid Tree)?

This page provides optimized solutions for LeetCode problem 261 (Graph Valid Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 261 (Graph Valid Tree)?

The time complexity for LeetCode 261 (Graph Valid Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 261 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 261 in Java, C++, or Python.

Back to LeetCode Solutions