Find Largest Value in Each Tree Row

📋

Problem

Imagine you are analyzing a forest canopy and want to find the tallest tree visible at each horizontal layer. This problem mimics that by finding the largest value at each level of a binary tree.

Given the root of a binary tree, return an array of the largest value in each row (level) of the tree. The root is considered level 0, its children level 1, and so on.

The number of nodes in the tree is in the range [1, 10^5].Node values are integers in the range [-2^31, 2^31 - 1].

Edge cases: Single node tree → output is the root valueAll nodes have the same value → output is repeated value per levelTree is skewed (all left or all right) → output is values along that path

</>

IDE

def largestValues(root: Optional[TreeNode]) -> List[int]:public List<Integer> largestValues(TreeNode root)vector<int> largestValues(TreeNode* root)function largestValues(root)

def largestValues(root):
    # Write your solution here
    pass

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<int> largestValues(TreeNode* root) {
    // Write your solution here
    return {};
}

function largestValues(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1, 2, 3]Taking the first node value per level instead of the maximum.✅ Update max value at each level by comparing all nodes before moving to next level.

Wrong: [1, 3, 17]Summing values at each level instead of taking maximum.✅ Use max function to track largest value per level, not sum.

Wrong: []Not handling single node or empty tree input correctly.✅ Return list with root value if tree is not empty; handle null root case explicitly.

Wrong: [5, 5]Incorrect level counting causing missing last level in skewed tree.✅ Ensure traversal continues until all levels are processed, even if only one node per level.

Wrong: TLE or timeoutUsing exponential or repeated traversal instead of O(n) BFS/DFS.✅ Implement BFS or DFS with level tracking to achieve O(n) time complexity.

✓

Test Cases

Focus on handling minimal and boundary inputs correctly.

Think about common algorithmic pitfalls like greedy mistakes and negative values.

Optimize your solution to run in linear time with respect to the number of nodes.

t1_01basic

Input{"root":[1,3,2,5,3,null,9]}

Expected[1,3,9]

⏱ Performance - must finish in 2000ms

Level 0 has value 1, level 1 has values 3 and 2 (max 3), level 2 has values 5, 3, and 9 (max 9).

💡 Use a breadth-first search (BFS) to traverse the tree level by level.

💡 At each level, track the maximum node value encountered.

💡 Return the list of maximum values collected from each level.

Why it failed: Output incorrect for canonical example - likely not tracking max per level correctly. Fix by updating max value at each level during BFS or DFS.

✓ Correctly computes max value per tree row using level order traversal.

t1_02basic

Input{"root":[4,1,7,0,2,6,9]}

Expected[4,7,9]

⏱ Performance - must finish in 2000ms

Level 0 max is 4; level 1 max is max(1,7)=7; level 2 max is max(0,2,6,9)=9.

💡 Traverse the tree level by level using a queue.

💡 At each level, compare all node values to find the maximum.

💡 Collect and return the maximum values for each level.

Why it failed: Incorrect max values per level - possibly mixing levels or not resetting max at each level. Fix by resetting max at start of each level iteration.

✓ Correctly identifies largest values at each tree row.

t2_01edge

Input{"root":[10]}

Expected[10]

⏱ Performance - must finish in 2000ms

Single node tree; output is the root value itself.

💡 Check how your code handles trees with only one node.

💡 Ensure the base case returns the root value as the only level max.

💡 Return a list containing just the root's value.

Why it failed: Fails single node case - likely returns empty or incorrect list. Fix by handling root-only tree correctly.

✓ Handles single node tree correctly.

t2_02edge

Input{"root":[5,5,5,5,5,5,5]}

Expected[5,5,5]

⏱ Performance - must finish in 2000ms

All nodes have the same value 5; max per level is 5 repeated.

💡 Test if your code correctly handles identical values at all nodes.

💡 Max per level should be the repeated node value.

💡 Ensure max updates correctly even if values are equal.

Why it failed: Fails identical values case - possibly skips updating max when equal. Fix by using max comparison inclusive of equality.

✓ Correctly handles all nodes with identical values.

t2_03edge

Input{"root":[1,2,null,3,null,4,null,5]}

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

⏱ Performance - must finish in 2000ms

Skewed tree (all left children); output is values along the path.

💡 Check if your traversal handles skewed trees correctly.

💡 Each level contains exactly one node in this case.

💡 Return the values in order from root to deepest leaf.

Why it failed: Fails skewed tree - possibly assumes multiple nodes per level. Fix by handling levels with single nodes correctly.

✓ Correctly processes skewed trees.

t3_01corner

Input{"root":[1,3,2,5,3,null,-1]}

Expected[1,3,5]

⏱ Performance - must finish in 2000ms

Level 2 has values 5, 3, and -1; max is 5, not sum or min.

💡 Ensure you are taking the maximum, not sum or minimum, at each level.

💡 Check your aggregation logic for level values.

💡 Use max function to update level max correctly.

Why it failed: Incorrect output due to summing or taking min instead of max at levels. Fix by using max aggregation per level.

✓ Correctly computes max ignoring negative values.

t3_02corner

Input{"root":[1,3,2,5,3,null,9,10]}

Expected[1,3,9,10]

⏱ Performance - must finish in 2000ms

Greedy trap: max at level 2 is 9, not 5 or 3; level 3 has 10.

💡 Beware of greedy approaches that pick first max found per level.

💡 Traverse entire level before deciding max.

💡 Use BFS queue to process all nodes at each level.

Why it failed: Fails greedy trap by not checking all nodes per level. Fix by processing entire level before max selection.

✓ Correctly avoids greedy trap by full level traversal.

t3_03corner

Input{"root":[0,-1,-2,-3,-4,-5,-6]}

Expected[0,-1,-3]

⏱ Performance - must finish in 2000ms

Handles negative values correctly; max at level 2 is -3 (max of -3,-4,-5,-6).

💡 Check that negative values are handled correctly in max comparisons.

💡 Do not assume all values are positive.

💡 Use max function that works with negative integers.

Why it failed: Fails negative values by ignoring or mishandling negatives. Fix by using correct max comparison for negatives.

✓ Correctly handles negative node values.

t4_01performance

Input{"root":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}

Expectednull

⏱ Performance - must finish in 2000ms

Large balanced tree with 100 nodes; solution must run in O(n) time within 2 seconds.

💡 Use BFS or DFS with level tracking for O(n) time complexity.

💡 Avoid repeated traversals or nested loops over nodes.

💡 Use a queue or recursion with level parameter to track max per level.

Why it failed: Solution times out due to exponential or inefficient traversal. Fix by implementing O(n) BFS or DFS with level tracking.

✓ Solution runs efficiently in O(n) time for large input.

Practice

1. You are given a binary tree and asked to compute the average value of nodes on each level. Which algorithmic approach guarantees an optimal solution that processes nodes level-by-level and efficiently computes these averages?

easy

A. Depth-first search (DFS) without tracking levels, summing all nodes and dividing by total count.

B. Breadth-first search (BFS) using a queue to traverse nodes level-by-level, summing values per level and dividing by the number of nodes at that level.

C. Greedy approach that picks the maximum node value at each level and averages those maximums.

D. Dynamic programming that stores partial sums of subtrees and combines them bottom-up.

Solution

1. Step 1: Understand the problem requires level-wise aggregation

   The problem asks for averages per level, so nodes must be grouped by their depth in the tree.

2. Step 2: Identify BFS as the natural approach for level order traversal

   BFS uses a queue to process nodes level-by-level, allowing summing and counting nodes at each level before moving on.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   BFS naturally groups nodes by level, enabling correct average calculation [OK]

Hint: Level order traversal = BFS with queue [OK]

Common Mistakes:

• Using DFS without level tracking loses level grouping
• Greedy max per level ignores all other nodes
• Bottom-up DP is unnecessary and complex here

2. You are given a binary tree where each node may have zero, one, or two children. Your task is to connect each node's next pointer to its next right node on the same level. If there is no next right node, the next pointer should be set to NULL. Which approach guarantees an optimal solution with O(n) time and O(h) space, where h is the tree height?

easy

A. Use a dynamic programming approach to store connections and build them bottom-up.

B. Perform a level order traversal using a queue to connect nodes level by level.

C. Use a recursive top-down approach that leverages already established next pointers to connect nodes without extra queue space.

D. Apply a greedy approach that connects nodes as soon as they are discovered during DFS.

Solution

1. Step 1: Understand the problem constraints

   The problem requires connecting next pointers in any binary tree, not necessarily perfect or complete, with O(n) time and O(h) space.

2. Step 2: Evaluate approaches

   Using a queue (Perform a level order traversal using a queue to connect nodes level by level.) uses O(n) space, violating the space constraint. DP (Use a dynamic programming approach to store connections and build them bottom-up.) is not applicable here. Greedy DFS (Apply a greedy approach that connects nodes as soon as they are discovered during DFS.) fails to guarantee correct connections across siblings at the same level. The recursive top-down approach (Use a recursive top-down approach that leverages already established next pointers to connect nodes without extra queue space.) uses existing next pointers to traverse levels efficiently with O(h) recursion stack space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Top-down recursion with next pointers -> O(n) time, O(h) space [OK]

Hint: Top-down recursion uses next pointers to avoid extra space [OK]

Common Mistakes:

• Assuming BFS with queue is optimal space-wise
• Trying DP bottom-up which doesn't fit this problem
• Using DFS greedily without next pointers

3. You are given a perfect binary tree where each node has two children. The task is to connect each node's next pointer to its immediate right neighbor on the same level, or NULL if there is none. Which approach guarantees an optimal solution with O(1) extra space and O(n) time complexity?

easy

A. Use the already established next pointers to traverse each level and connect children without extra space.

B. Perform a level order traversal using a queue to connect nodes at each level.

C. Apply a dynamic programming approach to store and connect nodes level-wise.

D. Use a depth-first search recursion to connect nodes from top to bottom.

Solution

1. Step 1: Understand the problem constraints

   The tree is perfect, so every node has two children, and all leaves are at the same level.

2. Step 2: Identify the approach that uses constant extra space

   Using next pointers already set on the current level to connect the next level avoids extra data structures like queues.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Optimal approach uses existing pointers to traverse levels [OK]

Hint: Use next pointers to traverse levels without extra space [OK]

Common Mistakes:

• Assuming BFS with queue is optimal space-wise
• Confusing DFS recursion with constant space
• Using DP which is unrelated

4. What is the time complexity of the optimal BFS approach with indexing and normalization to find the maximum width of a binary tree with n nodes?

medium

A. O(n log n) because of sorting indices at each level

B. O(n) because each node is visited exactly once in BFS

C. O(n^2) due to repeated index normalization at each level

D. O(n) but with extra O(n) space for the queue and index tracking

Solution

1. Step 1: Analyze BFS traversal

   Each node is enqueued and dequeued exactly once, so BFS visits all n nodes in O(n) time.

2. Step 2: Consider index normalization cost

   Index normalization is a constant-time arithmetic operation per node, not sorting or scanning the entire level.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time traversal with constant work per node [OK]

Hint: BFS visits each node once, normalization is O(1) per node [OK]

Common Mistakes:

• Assuming sorting indices per level adds log factor
• Confusing normalization with expensive operations
• Mistaking queue size for nested loops causing O(n^2)

5. Suppose the problem is extended so that the tree nodes can have multiple children (not just binary), and you need to check if the tree is symmetric around its center. Which modification to the BFS approach is necessary to correctly handle this case?

hard

A. Enqueue children in normal order and compare corresponding children pairs directly

B. Enqueue children in mirrored order and compare pairs from opposite ends of the children list

C. Use a recursive approach only, as BFS cannot handle multiple children

D. Check symmetry only at the root level and ignore deeper levels

Solution

1. Step 1: Understand symmetry in multi-child trees

   Symmetry means the first child on the left subtree mirrors the last child on the right subtree, second mirrors second last, etc.

2. Step 2: Modify BFS to enqueue children in mirrored order

   Enqueue children pairs from opposite ends of the children list to compare mirrored positions correctly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Mirrored enqueue order for multiple children preserves symmetry checks [OK]

Hint: Multi-child symmetry requires mirrored child pair comparisons [OK]

Common Mistakes:

• Enqueuing children in normal order causing false positives
• Assuming BFS cannot be adapted for multi-child trees
• Ignoring deeper levels of the tree