How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Implement DFS and tree algorithms | Amazon Coding Question

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.

Input: (1, [])

Expected Output: [[0]]

Explanation: Single isolated node.

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

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

Explanation: Edge 1-4 merges {0,1} and {4,5} into one component.

Input: (3, [[0, 2]])

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

Explanation: Node 1 is isolated and sorts after the {0,2} component.

Hints

Build an adjacency list first so each DFS expands in O(degree).
Maintain a global visited array; start a fresh DFS from every unvisited node.
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.

Input: ([],)

Expected Output: []

Explanation: Empty tree returns an empty list.

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

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

Explanation: 4 is left child of 2; 5 is right child of 3.

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

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

Explanation: Fully left-skewed chain: one node per level.

Hints

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).
For the traversal, process the BFS queue one level at a time by snapshotting len(queue) before the inner loop.
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.

Input: ([],)

Expected Output: True

Explanation: An empty tree is balanced.

Input: ([1],)

Expected Output: True

Explanation: A single node is trivially balanced.

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

Expected Output: False

Explanation: Left-skewed chain of height 4 vs right height 0 at the root.

Hints

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

Quick Overview