261. Graph Valid Tree

At a Glance

Topic: graphs
Pattern: Union-Find or DFS connectivity
Difficulty: Medium
Companies: Amazon, Google, Microsoft, LinkedIn, Meta
Frequency: Medium
LeetCode: 261 (Premium)

Problem (one-liner)

Given n nodes labeled 0..n-1 and undirected edges, return whether edges form a tree: connected, exactly n-1 edges, acyclic.

Recognition Cues

Tree ⇔ connected + |E| = n-1 + no cycles
Quick cycle check while union-ing

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

DFS count nodes vs edges — verify connectivity — O(n+e).
Union-Find — if union hits already-connected vertices, cycle — O(n α(n)).

Optimal Solution

Go

type unionFind struct {
	parent []int
	rank   []int
}

func newUnionFind(size int) *unionFind {
	parent := make([]int, size)
	rank := make([]int, size)
	for index := range parent {
		parent[index] = index
	}
	return &unionFind{parent: parent, rank: rank}
}

func (finder *unionFind) find(node int) int {
	if finder.parent[node] != node {
		finder.parent[node] = finder.find(finder.parent[node])
	}
	return finder.parent[node]
}

func (finder *unionFind) union(left int, right int) bool {
	rootLeft := finder.find(left)
	rootRight := finder.find(right)
	if rootLeft == rootRight {
		return false
	}
	if finder.rank[rootLeft] < finder.rank[rootRight] {
		rootLeft, rootRight = rootRight, rootLeft
	}
	finder.parent[rootRight] = rootLeft
	if finder.rank[rootLeft] == finder.rank[rootRight] {
		finder.rank[rootLeft]++
	}
	return true
}

func validTree(nodeCount int, edges [][]int) bool {
	if len(edges) != nodeCount-1 {
		return false
	}
	finder := newUnionFind(nodeCount)
	for _, edge := range edges {
		left := edge[0]
		right := edge[1]
		if !finder.union(left, right) {
			return false
		}
	}
	root := finder.find(0)
	for node := 1; node < nodeCount; node++ {
		if finder.find(node) != root {
			return false
		}
	}
	return true
}

JavaScript

class UnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, index) => index);
    this.rank = new Array(size).fill(0);
  }

  find(node) {
    if (this.parent[node] !== node) {
      this.parent[node] = this.find(this.parent[node]);
    }
    return this.parent[node];
  }

  union(left, right) {
    let rootLeft = this.find(left);
    let rootRight = this.find(right);
    if (rootLeft === rootRight) {
      return false;
    }
    if (this.rank[rootLeft] < this.rank[rootRight]) {
      [rootLeft, rootRight] = [rootRight, rootLeft];
    }
    this.parent[rootRight] = rootLeft;
    if (this.rank[rootLeft] === this.rank[rootRight]) {
      this.rank[rootLeft] += 1;
    }
    return true;
  }
}

function validTree(nodeCount, edges) {
  if (edges.length !== nodeCount - 1) {
    return false;
  }
  const finder = new UnionFind(nodeCount);
  for (const edge of edges) {
    const [left, right] = edge;
    if (!finder.union(left, right)) {
      return false;
    }
  }
  const root = finder.find(0);
  for (let node = 1; node < nodeCount; node += 1) {
    if (finder.find(node) !== root) {
      return false;
    }
  }
  return true;
}

Walkthrough

Edge count must be n-1; each successful union merges components; duplicate roots mid-edge ⇒ cycle; final single root ⇒ connected.

Invariant: With n-1 edges and no union rejection, tree has exactly one component.

Edge Cases

n = 1, empty edges — valid tree
Disconnected extra edges — fails connectivity check

Pitfalls

Checking only n-1 edges without cycle detection — could still have cycle if repeated vertex pairing forms loop with extras—actually with exactly n-1 edges, connected iff acyclic; still union-find catches cycles early

Variants

Directed rooted tree validation — different constraints

Mind-Map Tags

#union-find #tree #cycle #connectivity #edges-count