#47 · Graphs

Graph Valid Tree

Given n nodes labelled 0 to n − 1 and a list of undirected edges, check whether the edges form a valid tree: connected, with no cycles.

MediumLeetCode

Current
On path / queued
Done
Cycle / blocked

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Tree characterisation

For an undirected graph on n nodes these are equivalent: it is a tree; it is connected with n − 1 edges; it has n − 1 edges and no cycle. Any two of "connected", "acyclic", "exactly n − 1 edges" imply the third.

Memory layout

Nothing is stored: it is a counting argument. Checking the edge count first costs O(1).

Operation	Cost
edge-count test	O(1)

Union-Find (disjoint set union)

Maintains which nodes are already connected. Joining the two ends of an edge is safe only if they were in different sets; if they already share a leader, the edge would create a cycle.

Memory layout

parent[] (and optionally size[]) integer arrays of length n.

Operation	Cost
find / union	O(α(n)), practically constant

Why it fits

With exactly n − 1 edges, "no cycle" already forces "connected" (and vice versa), so one test is enough once the count is right.
Union-Find answers "were these two nodes already connected?" for every edge in almost constant time, so a cycle is spotted the moment its last edge appears.
A traversal needs the adjacency list and a parent check to avoid mistaking the edge you just crossed for a cycle; Union-Find avoids that subtlety.

Why alternatives degrade

Only checking connectivity:: A connected graph with extra edges has a cycle and is not a tree.
Only counting edges:: n − 1 edges can still be a triangle plus separate pair (like the example): cycle and disconnected.
DFS without a parent argument:: Every undirected edge is seen from both ends, so a plain visited check reports a false cycle on the first step back.

Four approaches, from naive to production

1 · beginner

DFS: find a cycle, then check connectivity

time O(n + e)space O(n + e)

Build an adjacency list. Run a depth-first search from node 0 that remembers the node it came from; seeing a visited node that is not the parent means a cycle. If there is no cycle, the graph is a tree exactly when the search reached all n nodes.

bool validTree(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    set<int> visited;
    function<bool(int, int)> hasCycle = [&](int node, int parent) -> bool {
        visited.insert(node);
        for (int next : adj[node]) {
            if (next == parent) continue;
            if (visited.count(next) || hasCycle(next, node)) return true;
        }
        return false;
    };
    if (hasCycle(0, -1)) return false;
    return (int)visited.size() == n;
}

public boolean validTree(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    Set<Integer> visited = new HashSet<>();
    if (hasCycle(adj, visited, 0, -1)) return false;
    return visited.size() == n;
}
private boolean hasCycle(List<List<Integer>> adj, Set<Integer> visited, int node, int parent) {
    visited.add(node);
    for (int next : adj.get(node)) {
        if (next == parent) continue;
        if (visited.contains(next) || hasCycle(adj, visited, next, node)) return true;
    }
    return false;
}

def valid_tree(n, edges):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    visited = set()
    def has_cycle(node, parent):
        visited.add(node)
        for nxt in adj[node]:
            if nxt == parent: continue
            if nxt in visited or has_cycle(nxt, node): return True
        return False
    if has_cycle(0, -1): return False
    return len(visited) == n

function validTree(n: number, edges: number[][]): boolean {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  const visited = new Set<number>();
  const hasCycle = (node: number, parent: number): boolean => {
    visited.add(node);
    for (const next of adj[node]) {
      if (next === parent) continue;
      if (visited.has(next) || hasCycle(next, node)) return true;
    }
    return false;
  };
  if (hasCycle(0, -1)) return false;
  return visited.size === n;
}

Flaws & bottlenecks

Needs the adjacency list (extra memory) before any checking.
Recursion depth can reach n for a long path.
Forgetting the parent exception makes every edge look like a cycle.

Interviewer cross-questions

Why pass the parent into the recursion?

Say: Each undirected edge is listed in both endpoints. Without the parent check, the DFS would return along the same edge and treat it as a second route.

Why check visited.size === n at the end?

Say: No cycle only proves the reached part is a tree (a forest if the graph is split). All n nodes must be reached for one connected tree.

Can you avoid recursion?

Say: Yes: use an explicit stack or a queue (BFS) and store each node's parent.

2 · intermediate

BFS with a parent table

time O(n + e)space O(n + e)

Run a breadth-first search from node 0 and record the parent of each discovered node. A neighbour that is already discovered and is not the current node's parent closes a cycle. Count discovered nodes and compare with n at the end.

bool validTree(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    vector<int> parent(n, -2);
    parent[0] = -1;
    vector<int> queue = {0};
    size_t head = 0;
    int seen = 1;
    while (head < queue.size()) {
        int node = queue[head++];
        for (int next : adj[node]) {
            if (next == parent[node]) continue;
            if (parent[next] != -2) return false;
            parent[next] = node;
            seen++;
            queue.push_back(next);
        }
    }
    return seen == n;
}

public boolean validTree(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    int[] parent = new int[n];
    Arrays.fill(parent, -2);
    parent[0] = -1;
    List<Integer> queue = new ArrayList<>(); queue.add(0);
    int head = 0;
    int seen = 1;
    while (head < queue.size()) {
        int node = queue.get(head++);
        for (int next : adj.get(node)) {
            if (next == parent[node]) continue;
            if (parent[next] != -2) return false;
            parent[next] = node;
            seen++;
            queue.add(next);
        }
    }
    return seen == n;
}

def valid_tree(n, edges):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    parent = [-2] * n
    parent[0] = -1
    queue = [0]
    head = 0
    seen = 1
    while head < len(queue):
        node = queue[head]
        head += 1
        for nxt in adj[node]:
            if nxt == parent[node]: continue
            if parent[nxt] != -2: return False
            parent[nxt] = node
            seen += 1
            queue.append(nxt)
    return seen == n

function validTree(n: number, edges: number[][]): boolean {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  const parent = new Array<number>(n).fill(-2);
  parent[0] = -1;
  const queue: number[] = [0];
  let head = 0;
  let seen = 1;
  while (head < queue.length) {
    const node = queue[head++];
    for (const next of adj[node]) {
      if (next === parent[node]) continue;
      if (parent[next] !== -2) return false;
      parent[next] = node;
      seen++;
      queue.push(next);
    }
  }
  return seen === n;
}

Flaws & bottlenecks

Still builds an adjacency list first.
The -2 sentinel for "unvisited" next to -1 for "root" is easy to confuse.
Handles at most one component: a disconnected graph is only detected by the final count.

Interviewer cross-questions

Why does a second route to a node mean a cycle?

Say: In a tree there is exactly one path between any two nodes. If BFS reaches a node by a second path, two different paths exist, which is a cycle.

How is this different from the DFS version?

Say: The queue replaces the recursion, so there is no depth limit, and the parent is stored in a table instead of an argument.

What does the final comparison catch?

Say: Nodes the search never reached: the graph is disconnected even if the reached part is acyclic.

3 · advanced

Union-Find + edge-count check

time O(n · α(n))space O(n)

Reject unless there are exactly n − 1 edges. Then process each edge with Union-Find: if the two ends already have the same leader the edge makes a cycle; otherwise join them. After n − 1 successful joins the graph is a single tree.

bool validTree(int n, vector<vector<int>>& edges) {
    if ((int)edges.size() != n - 1) return false;
    vector<int> parent(n); iota(parent.begin(), parent.end(), 0);
    function<int(int)> find = [&](int x) -> int {
        return parent[x] == x ? x : (parent[x] = find(parent[x]));
    };
    for (auto& e : edges) {
        int ra = find(e[0]), rb = find(e[1]);
        if (ra == rb) return false;
        parent[ra] = rb;
    }
    return true;
}

public boolean validTree(int n, int[][] edges) {
    if (edges.length != n - 1) return false;
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    for (int[] e : edges) {
        int ra = find(parent, e[0]), rb = find(parent, e[1]);
        if (ra == rb) return false;
        parent[ra] = rb;
    }
    return true;
}
private int find(int[] parent, int x) {
    if (parent[x] != x) parent[x] = find(parent, parent[x]);
    return parent[x];
}

def valid_tree(n, edges):
    if len(edges) != n - 1: return False
    parent = list(range(n))
    def find(x):
        if parent[x] != x: parent[x] = find(parent[x])
        return parent[x]
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb: return False
        parent[ra] = rb
    return True

function validTree(n: number, edges: number[][]): boolean {
  if (edges.length !== n - 1) return false;
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x])));
  for (const [a, b] of edges) {
    const ra = find(a), rb = find(b);
    if (ra === rb) return false;
    parent[ra] = rb;
  }
  return true;
}

Flaws & bottlenecks

Recursive find with path compression could recurse deeply on an adversarial chain (a few thousand nodes is fine; millions needs an iterative find).
Joining without union by size can build tall trees before compression helps.
It does not tell you where the cycle is, only that one exists.

Interviewer cross-questions

Why check n − 1 edges first?

Say: It is O(1) and rules out every graph with too few edges (necessarily disconnected) or too many (necessarily cyclic) before any work is done.

Why is no cycle plus n − 1 edges enough?

Say: An acyclic graph with n nodes and n − 1 edges has exactly one connected component, so it is a tree.

What is path compression?

Say: During find, every node on the path is pointed straight at the leader. Later finds on those nodes take one step.

4 · expert

Union by size, path halving, typed arrays

time O(n · α(n))space O(n)

Same Union-Find in flat integer arrays. find halves paths iteratively (no recursion), and each merge hangs the smaller set under the bigger one, which keeps trees at logarithmic height without relying on compression.

bool validTree(int n, vector<vector<int>>& edges) {
    if ((int)edges.size() != n - 1) return false;
    vector<int> parent(n);
    vector<int> size(n, 1);
    for (int i = 0; i < n; i++) parent[i] = i;
    auto find = [&](int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    for (int i = 0; i < (int)edges.size(); i++) {
        int a = find(edges[i][0]), b = find(edges[i][1]);
        if (a == b) return false;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a;
        size[a] += size[b];
    }
    return true;
}

public boolean validTree(int n, int[][] edges) {
    if (edges.length != n - 1) return false;
    int[] parent = new int[n];
    int[] size = new int[n];
    Arrays.fill(size, 1);
    for (int i = 0; i < n; i++) parent[i] = i;
    for (int i = 0; i < edges.length; i++) {
        int a = find(parent, edges[i][0]), b = find(parent, edges[i][1]);
        if (a == b) return false;
        if (size[a] < size[b]) { int t = a; a = b; b = t; }
        parent[b] = a;
        size[a] += size[b];
    }
    return true;
}
private int find(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

def valid_tree(n, edges):
    if len(edges) != n - 1: return False
    parent = list(range(n))
    size = [1] * n
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    for i in range(len(edges)):
        a, b = find(edges[i][0]), find(edges[i][1])
        if a == b: return False
        if size[a] < size[b]: a, b = b, a
        parent[b] = a
        size[a] += size[b]
    return True

function validTree(n: number, edges: number[][]): boolean {
  if (edges.length !== n - 1) return false;
  const parent = new Int32Array(n);
  const size = new Int32Array(n).fill(1);
  for (let i = 0; i < n; i++) parent[i] = i;
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  };
  for (let i = 0; i < edges.length; i++) {
    let a = find(edges[i][0]), b = find(edges[i][1]);
    if (a === b) return false;
    if (size[a] < size[b]) [a, b] = [b, a];
    parent[b] = a;
    size[a] += size[b];
  }
  return true;
}

Flaws & bottlenecks

More code and more places for off-by-one mistakes (swap, size update).
The gain over plain path compression is small for interview-sized input.
Assumes node labels are valid indices 0 … n − 1; a production version would validate them.

Interviewer cross-questions

Why union by size?

Say: It guarantees a tree of height at most log₂ n, so even a single find without compression is fast. Combined with path halving it gives near-constant amortized time.

Why iterative find?

Say: It avoids recursion depth limits and function-call overhead, which matters when n is large.

What happens with a self-loop edge such as [2, 2]?

Say: find(2) equals find(2), so it is reported as a cycle immediately, which is correct: a self-loop is a cycle.

Synchronized code walkthrough

Showing: DFS: find a cycle, then check connectivity — shares the player above; click any step to jump.

bool validTree(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    set<int> visited;
    function<bool(int, int)> hasCycle = [&](int node, int parent) -> bool {
        visited.insert(node);
        for (int next : adj[node]) {
            if (next == parent) continue;
            if (visited.count(next) || hasCycle(next, node)) return true;
        }
        return false;
    };
    if (hasCycle(0, -1)) return false;
    return (int)visited.size() == n;
}

public boolean validTree(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    Set<Integer> visited = new HashSet<>();
    if (hasCycle(adj, visited, 0, -1)) return false;
    return visited.size() == n;
}
private boolean hasCycle(List<List<Integer>> adj, Set<Integer> visited, int node, int parent) {
    visited.add(node);
    for (int next : adj.get(node)) {
        if (next == parent) continue;
        if (visited.contains(next) || hasCycle(adj, visited, next, node)) return true;
    }
    return false;
}

def valid_tree(n, edges):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    visited = set()
    def has_cycle(node, parent):
        visited.add(node)
        for nxt in adj[node]:
            if nxt == parent: continue
            if nxt in visited or has_cycle(nxt, node): return True
        return False
    if has_cycle(0, -1): return False
    return len(visited) == n

function validTree(n: number, edges: number[][]): boolean {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  const visited = new Set<number>();
  const hasCycle = (node: number, parent: number): boolean => {
    visited.add(node);
    for (const next of adj[node]) {
      if (next === parent) continue;
      if (visited.has(next) || hasCycle(next, node)) return true;
    }
    return false;
  };
  if (hasCycle(0, -1)) return false;
  return visited.size === n;
}

bool validTree(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    vector<int> parent(n, -2);
    parent[0] = -1;
    vector<int> queue = {0};
    size_t head = 0;
    int seen = 1;
    while (head < queue.size()) {
        int node = queue[head++];
        for (int next : adj[node]) {
            if (next == parent[node]) continue;
            if (parent[next] != -2) return false;
            parent[next] = node;
            seen++;
            queue.push_back(next);
        }
    }
    return seen == n;
}

public boolean validTree(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    int[] parent = new int[n];
    Arrays.fill(parent, -2);
    parent[0] = -1;
    List<Integer> queue = new ArrayList<>(); queue.add(0);
    int head = 0;
    int seen = 1;
    while (head < queue.size()) {
        int node = queue.get(head++);
        for (int next : adj.get(node)) {
            if (next == parent[node]) continue;
            if (parent[next] != -2) return false;
            parent[next] = node;
            seen++;
            queue.add(next);
        }
    }
    return seen == n;
}

def valid_tree(n, edges):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    parent = [-2] * n
    parent[0] = -1
    queue = [0]
    head = 0
    seen = 1
    while head < len(queue):
        node = queue[head]
        head += 1
        for nxt in adj[node]:
            if nxt == parent[node]: continue
            if parent[nxt] != -2: return False
            parent[nxt] = node
            seen += 1
            queue.append(nxt)
    return seen == n

function validTree(n: number, edges: number[][]): boolean {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  const parent = new Array<number>(n).fill(-2);
  parent[0] = -1;
  const queue: number[] = [0];
  let head = 0;
  let seen = 1;
  while (head < queue.length) {
    const node = queue[head++];
    for (const next of adj[node]) {
      if (next === parent[node]) continue;
      if (parent[next] !== -2) return false;
      parent[next] = node;
      seen++;
      queue.push(next);
    }
  }
  return seen === n;
}

bool validTree(int n, vector<vector<int>>& edges) {
    if ((int)edges.size() != n - 1) return false;
    vector<int> parent(n); iota(parent.begin(), parent.end(), 0);
    function<int(int)> find = [&](int x) -> int {
        return parent[x] == x ? x : (parent[x] = find(parent[x]));
    };
    for (auto& e : edges) {
        int ra = find(e[0]), rb = find(e[1]);
        if (ra == rb) return false;
        parent[ra] = rb;
    }
    return true;
}

public boolean validTree(int n, int[][] edges) {
    if (edges.length != n - 1) return false;
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    for (int[] e : edges) {
        int ra = find(parent, e[0]), rb = find(parent, e[1]);
        if (ra == rb) return false;
        parent[ra] = rb;
    }
    return true;
}
private int find(int[] parent, int x) {
    if (parent[x] != x) parent[x] = find(parent, parent[x]);
    return parent[x];
}

def valid_tree(n, edges):
    if len(edges) != n - 1: return False
    parent = list(range(n))
    def find(x):
        if parent[x] != x: parent[x] = find(parent[x])
        return parent[x]
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb: return False
        parent[ra] = rb
    return True

function validTree(n: number, edges: number[][]): boolean {
  if (edges.length !== n - 1) return false;
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x])));
  for (const [a, b] of edges) {
    const ra = find(a), rb = find(b);
    if (ra === rb) return false;
    parent[ra] = rb;
  }
  return true;
}

bool validTree(int n, vector<vector<int>>& edges) {
    if ((int)edges.size() != n - 1) return false;
    vector<int> parent(n);
    vector<int> size(n, 1);
    for (int i = 0; i < n; i++) parent[i] = i;
    auto find = [&](int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    for (int i = 0; i < (int)edges.size(); i++) {
        int a = find(edges[i][0]), b = find(edges[i][1]);
        if (a == b) return false;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a;
        size[a] += size[b];
    }
    return true;
}

public boolean validTree(int n, int[][] edges) {
    if (edges.length != n - 1) return false;
    int[] parent = new int[n];
    int[] size = new int[n];
    Arrays.fill(size, 1);
    for (int i = 0; i < n; i++) parent[i] = i;
    for (int i = 0; i < edges.length; i++) {
        int a = find(parent, edges[i][0]), b = find(parent, edges[i][1]);
        if (a == b) return false;
        if (size[a] < size[b]) { int t = a; a = b; b = t; }
        parent[b] = a;
        size[a] += size[b];
    }
    return true;
}
private int find(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

def valid_tree(n, edges):
    if len(edges) != n - 1: return False
    parent = list(range(n))
    size = [1] * n
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    for i in range(len(edges)):
        a, b = find(edges[i][0]), find(edges[i][1])
        if a == b: return False
        if size[a] < size[b]: a, b = b, a
        parent[b] = a
        size[a] += size[b]
    return True

function validTree(n: number, edges: number[][]): boolean {
  if (edges.length !== n - 1) return false;
  const parent = new Int32Array(n);
  const size = new Int32Array(n).fill(1);
  for (let i = 0; i < n; i++) parent[i] = i;
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  };
  for (let i = 0; i < edges.length; i++) {
    let a = find(edges[i][0]), b = find(edges[i][1]);
    if (a === b) return false;
    if (size[a] < size[b]) [a, b] = [b, a];
    parent[b] = a;
    size[a] += size[b];
  }
  return true;
}