Quick Overview

This question evaluates graph traversal and tree-algorithm competencies, specifically depth-first search for connected components and binary tree operations such as level-order traversal and height-balance checking, including complexity analysis and scalability considerations for very large sparse graphs.

Implement DFS and tree algorithms

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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.

Quick Answer: This question evaluates graph traversal and tree-algorithm competencies, specifically depth-first search for connected components and binary tree operations such as level-order traversal and height-balance checking, including complexity analysis and scalability considerations for very large sparse graphs.

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)

Examples

Input: (5, [[0, 1], [1, 2], [3, 4]])

Expected Output: [[0, 1, 2], [3, 4]]

Explanation: Nodes 0-1-2 form one component, 3-4 another.

Input: (4, [])

Expected Output: [[0], [1], [2], [3]]

Explanation: No edges: every node is its own singleton component.

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

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

Expected Output: [[3], [9, 20], [15, 7]]

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

Input: ([1],)

Expected 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

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

Expected Output: True

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

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

Expected 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.

Loading coding console...