515. Find Largest Value in Each Tree Row - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Given the root of a binary tree, return an array where each element is the largest value in its corresponding tree row (0‑indexed).

Examples

Example 1

Input      root = [1,3,2,5,3,null,9]  
Tree       ┌───┐  
              1  
             / \  
            3   2  
           / \   \  
          5   3   9  
Output     [1,3,9]  
Explanation  
 Row 0: [1]       → max = 1  
 Row 1: [3,2]     → max = 3  
 Row 2: [5,3,9]   → max = 9

Example 2

Input      root = [1,2,3]  
Tree       1  
           / \  
          2   3  
Output     [1,3]  
Explanation  
 Row 0: [1]     → 1  
 Row 1: [2,3]   → 3

Example 3

Input      root = []  
Output     []  
Explanation  Empty tree → no rows

Constraints

The number of nodes in the tree is in the range [0, 10⁴].
-2³¹ ≤ Node.val ≤ 2³¹−1

Hints

How would you traverse the tree row by row?
While visiting one row, how can you keep track of the maximum?
Can you do it in one pass using depth information and update a result list?

Approach 1 – Breadth‑First Search (Level‑Order)

Idea

Use a queue to process nodes level by level. For each level, record the size of the queue (number of nodes in that row), then pop exactly that many nodes, track the maximum value seen, and enqueue their children.

Steps

If root is null, return an empty list.
Initialize a queue with root and an empty result list.
While the queue is not empty:
1. Let levelSize = queue.size(), levelMax = -∞.
2. Loop levelSize times:
  - Pop node from the queue.
  - levelMax = max(levelMax, node.val).
  - If node.left exists, enqueue it.
  - If node.right exists, enqueue it.
3. Append levelMax to result.
Return result.

Code (Python)

Python3

. . . .

Complexity Analysis

Time: O(n) where n = number of nodes (each node is visited once).
Space: O(w) where w = maximum width of the tree (queue size).

Approach 2 – Depth‑First Search with Depth Tracking

Idea

Traverse the tree in pre‑order or in‑order, carrying a depth parameter. Maintain a result list where result[depth] is updated to the maximum seen at that depth. If you first visit a new depth, append the node’s value; otherwise, take the max.

Steps

Initialize an empty result list.
Define recursive dfs(node, depth):
- If node is null, return.
- If depth equals result.size(), append node.val; else result[depth] = max(result[depth], node.val).
- Call dfs(node.left, depth+1), then dfs(node.right, depth+1).
Call dfs(root, 0) and return result.

Code (Python)

Python3

. . . .

Code (Java)

Java

. . . .

Complexity Analysis

Time: O(n) (each node visited once).
Space: O(h) recursion stack, where h = tree height (worst O(n)).

Step‑by‑Step Walkthrough

For Example 1 tree:

BFS:
- Level 0: queue=[1] → max=1 → result=[1]
- Level 1: queue=[3,2] → max=3 → result=[1,3]
- Level 2: queue=[5,3,9] → max=9 → result=[1,3,9]
DFS:
- Visit (1, depth=0) → result=[1]
- Visit (3, depth=1) → result=[1,3]
- Visit (5, depth=2) → result=[1,3,5]
- Back to (3), visit right (3, depth=2) → result[2]=max(5,3)=5
- Back to root, visit (2, depth=1) → result[1]=max(3,2)=3
- Visit right.right (9, depth=2) → result[2]=max(5,9)=9
- Final result=[1,3,9]

Common Mistakes

Reinitializing the level max inside the inner loop incorrectly (e.g. forgetting to reset per level).
Off‑by‑one depth indexing in DFS (mixing 0‑ and 1‑based depths).
Modifying the tree or using global/static variables without resetting between calls.