Is This Graph a Tree

Read at your own pace. Code execution, quizzes, progress tracking, and the AI tutor are available in the interactive view with JavaScript enabled.

Description

Given an undirected graph, can you see if it's a tree? If so, return true and false otherwise.

An undirected graph is a tree based on the following conditions: first, there cannot be a cycle. Second, the graph must be connected.

This is an example of a graph that is a tree:

1 - 2
    |
    3 - 4

This one is an example of one that is not:

You'll be given two parameters: n for number of nodes, and a multidimensional array of edges like such: [[1, 2], [2, 3]], each pair representing the vertices connected by the edge.

Constraints

Number of vertices in the graph <= 100000
Number of edges <= 100000
The array edges can be empty
Expected time complexity : O(|V| + |E|) where |V| be the number of nodes n in the graph and |E| to be the number of edges in the graph
Expected space complexity : O(|V|)

```js
function isGraphTree(n, edges) {
  const unions = [];
  for (let i = 0; i < n; i++) {
    unions.push(i);
  }

  for (i = 0; i < edges.length; i++) {
    const edge = edges[i];
    if (isConnected(unions, edge[1], edge[0])) {
      return false;
    }
  }

  let visited = {};
  let diff = 0;

  for (i = 0; i < unions.length; i++) {
    let union = unions[i];
    if (visited[union]) {
      continue;
    }

    visited[union] = true;
    diff++;
  }

  return diff === 1;
}

function isConnected(unions, i, j) {
  let group1 = unions[i];
  let group2 = unions[j];

  if (group1 === group2) {
    return true;
  }

  for (let k = 0; k < unions.length; k++) {
    if (unions[k] === group2) {
      unions[k] = group1;
    }
  }

  return false;
}
```

java
```java
public class Main {
    public static void main(String[] args) {
        // Driver code here
    }

    static boolean isGraphTree(int n, int[][] edges) {
        int[] unions = new int[n];
        for (int i = 0; i < n; i++) {
            unions[i] = i;
        }

        for (int i = 0; i < edges.length; i++) {
            int[] edge = edges[i];
            if (isConnected(unions, edge[1], edge[0])) {
                return false;
            }
        }

        boolean[] visited = new boolean[n];
        int diff = 0;

        for (int i = 0; i < unions.length; i++) {
            int union = unions[i];
            if (visited[union]) {
                continue;
            }

            visited[union] = true;
            diff++;
        }

        return diff == 1;
    }

    static boolean isConnected(int[] unions, int i, int j) {
        int group1 = unions[i];
        int group2 = unions[j];

        if (group1 == group2) {
            return true;
        }

        for (int k = 0; k < unions.length; k++) {
            if (unions[k] == group2) {
                unions[k] = group1;
            }
        }

        return false;
    }
}
```
python
```python
def is_graph_tree(n, edges):
  unions = [i for i in range(n)]

  for edge in edges:
    if is_connected(unions, edge[1], edge[0]):
      return False

  visited = {}
  diff = 0

  for union in unions:
    if union in visited:
      continue

    visited[union] = True
    diff += 1

  return diff == 1


def is_connected(unions, i, j):
  group1 = unions[i]
  group2 = unions[j]

  if group1 == group2:
    return True

  for k in range(len(unions)):
    if unions[k] == group2:
      unions[k] = group1

  return False
```
cpp

```cpp
#include <vector>
#include <unordered_map>

bool isGraphTree(int n, std::vector<std::vector<int>>& edges) {
    std::vector<int> unions(n);
    for (int i = 0; i < n; i++) {
        unions[i] = i;
    }

    for (int i = 0; i < edges.size(); i++) {
        if (isConnected(unions, edges[i][1], edges[i][0])) {
            return false;
        }
    }

    std::unordered_map<int, bool> visited;
    int diff = 0;

    for (int i = 0; i < unions.size(); i++) {
        if (visited[unions[i]]) {
            continue;
        }

        visited[unions[i]] = true;
        diff++;
    }

    return diff == 1;
}

bool isConnected(std::vector<int>& unions, int i, int j) {
    int group1 = unions[i];
    int group2 = unions[j];

    if (group1 == group2) {
        return true;
    }

    for (int k = 0; k < unions.size(); k++) {
        if (unions[k] == group2) {
            unions[k] = group1;
        }
    }

    return false;
}
```
csharp
```csharp
class Solution {
    public bool IsGraphTree(int n, int[][] edges) {
        int[] unions = new int[n];
        for (int i = 0; i < n; i++) {
            unions[i] = i;
        }

        for (int i = 0; i < edges.Length; i++) {
            if (IsConnected(unions, edges[i][1], edges[i][0])) {
                return false;
            }
        }

        bool[] visited = new bool[n];
        int diff = 0;

        for (int i = 0; i < unions.Length; i++) {
            if (visited[unions[i]]) {
                continue;
            }

            visited[unions[i]] = true;
            diff++;
        }

        return diff == 1;
    }

    public bool IsConnected(int[] unions, int i, int j) {
        int group1 = unions[i];
        int group2 = unions[j];

        if (group1 == group2) {
            return true;
        }

        for (int k = 0; k < unions.Length; k++) {
            if (unions[k] == group2) {
                unions[k] = group1;
            }
        }

        return false;
    }
}
```
go
```go
func isGraphTree(n int, edges [][]int) bool {
    unions := make([]int, n)
    for i := 0; i < n; i++ {
        unions[i] = i
    }

    for _, edge := range edges {
        if isConnected(unions, edge[1], edge[0]) {
            return false
        }
    }

    visited := make(map[int]bool)
    diff := 0

    for _, union := range unions {
        if visited[union] {
            continue
        }

        visited[union] = true
        diff++
    }

    return diff == 1
}

func isConnected(unions []int, i int, j int) bool {
    group1 := unions[i]
    group2 := unions[j]

    if group1 == group2 {
        return true
    }

    for k := 0; k < len(unions); k++ {
        if unions[k] == group2 {
            unions[k] = group1
        }
    }

    return false
}
```

CONTINUE WITH ALGODAILY PREMIUM

Keep going with the complete tutorial.

Unlock the remaining explanations and exercises, alongside the full learning library.

Explore Premium →

Open interactive view →