Implement DFS and tree algorithms

Part 1 (DFS on graph): Given an undirected graph with n nodes labeled 0..n-1 and an edge list, implement a function that returns all connected components using depth-first search. Each component should be returned as a list of node labels in ascending order; the list of components should be sorted by each component’s smallest label. Discuss time/space complexity and how you would handle very large sparse graphs.

Part 2 (Binary tree): Given the root of a binary tree, implement (a) level-order traversal that returns values grouped by level, and (b) a function that determines whether the tree is height-balanced (for every node, the height difference between left and right subtrees is at most 1). Provide complexity and key test cases.

Connected Components via DFS

Given an undirected graph with n nodes labeled 0..n-1 and an edge list, return all connected components using depth-first search.

Each component must be returned as a list of node labels in ascending order, and the list of components must be sorted by each component's smallest label.

Example

n = 5, edges = [[0,1],[1,2],[3,4]]
-> [[0, 1, 2], [3, 4]]

Node 4 (and any node with no edges) forms its own singleton component.

Scaling note: For very large sparse graphs, use an adjacency list (O(n + E) memory) rather than an adjacency matrix (O(n^2)), and prefer an explicit stack or iterative DFS to avoid Python/JVM recursion-depth limits.

Constraints

• 1 <= n <= 10^5
• 0 <= number of edges <= 2 * 10^5
• edges are undirected; 0 <= u, v < n
• the graph may be disconnected (a forest of components, including isolated nodes)

Hints

1. Build an adjacency list first so each DFS expands in O(degree).
2. Maintain a global visited array; start a fresh DFS from every unvisited node.
3. Sort each component ascending, then sort the list of components by their first (smallest) element.

Binary Tree Level-Order Traversal

Given the root of a binary tree, return its node values grouped by level (top to bottom, left to right within each level).

The tree is provided as a level-order array using null (Python None) for missing children — the standard LeetCode serialization. For example [3, 9, 20, null, null, 15, 7] is:

      3
     / \
    9   20
        / \
       15  7

and should produce [[3], [9, 20], [15, 7]].

Return an empty list for an empty tree.

Constraints

• 0 <= number of nodes <= 2000
• node values fit in a 32-bit signed integer
• input is a valid level-order serialization with None for absent children

Examples

Example 1

Input: ([3, 9, 20, None, None, 15, 7],)
Output: [[3], [9, 20], [15, 7]]

Explanation: Classic 3-level tree; 15 and 7 are children of 20.

Example 2

Input: ([1],)
Output: [[1]]

Explanation: Single node, one level.

Hints

1. Reconstruct the tree from the level-order array using a build queue: pop a parent, attach the next two array entries as its children (skipping None).
2. For the traversal, process the BFS queue one level at a time by snapshotting len(queue) before the inner loop.
3. Append each level's values as its own list.

Check if a Binary Tree is Height-Balanced

Given the root of a binary tree, return true if it is height-balanced: for every node, the height difference between its left and right subtrees is at most 1.

The tree is provided as a level-order array with null (Python None) for missing children, e.g. [3, 9, 20, null, null, 15, 7].

An empty tree is balanced.

Constraints

• 0 <= number of nodes <= 5000
• node values fit in a 32-bit signed integer
• input is a valid level-order serialization with None for absent children

Examples

Example 1

Input: ([3, 9, 20, None, None, 15, 7],)
Output: True

Explanation: Every subtree's left/right heights differ by at most 1.

Example 2

Input: ([1, 2, 2, 3, 3, None, None, 4, 4],)
Output: False

Explanation: The left subtree is two levels deeper than the right at the root.

Hints

1. Compute each node's height bottom-up in a single post-order pass instead of recomputing heights repeatedly (which would be O(n^2)).
2. At each node, if abs(leftHeight - rightHeight) > 1, mark the whole tree as unbalanced.
3. Return 1 + max(leftHeight, rightHeight) as the node's height; an empty subtree has height 0.