Find Largest Value in Each Tree Row

Medium · Graphs · Explanation and code example

Iterative DFS

How it works

The recursive DFS can be converted to an iterative approach using a stack. Each stack entry stores both the node and its level. This avoids recursion overhead while maintaining the same logic.

Steps

  1. If the root is null, return an empty list.
  2. Initialize a stack with (root, 0) and an empty result list.
  3. While the stack is not empty:
    • Pop (node, level) from the stack.
    • If level equals the result list size, append the node's value.
    • Otherwise, update res[level] to the maximum of its current value and the node's value.
    • Push the right child first (if exists), then the left child, both with level + 1.
  4. Return the result list.

Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

Things to watch for

Not Handling Empty Tree

Forgetting to check if the root is null before processing leads to null pointer exceptions or runtime errors. Always add an early return for the empty tree case, returning an empty list rather than attempting to traverse a non-existent tree.

Initializing Row Maximum Incorrectly

When tracking the maximum value for each row, initializing rowMax to 0 or a small positive number fails for trees with negative values. The correct approach is to initialize rowMax with the first node's value in that row, or use Integer.MIN_VALUE (or equivalent) to ensure negative values are handled correctly.

Mixing Up Level Boundaries in BFS

In BFS, you must process all nodes at the current level before moving to the next. A common mistake is not capturing the queue size before the inner loop, causing nodes from the next level to be processed prematurely. Always store queue.size() at the start of each level iteration and use that fixed count for the inner loop.

Python code example

from typing import List, Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        res = []
        stack = [(root, 0)]
        while stack:
            node, level = stack.pop()
            if level == len(res):
                res.append(node.val)
            else:
                res[level] = max(res[level], node.val)

            if node.right:
                stack.append((node.right, level + 1))
            if node.left:
                stack.append((node.left, level + 1))

        return res

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        if (!root) return {};

        vector<int> res;
        stack<pair<TreeNode*, int>> stk;
        stk.push({root, 0});
        while (!stk.empty()) {
            auto [node, level] = stk.top();stk.pop();
            if (level == res.size()) {
                res.push_back(node->val);
            } else {
                res[level] = max(res[level], node->val);
            }

            if (node->right) stk.push({node->right, level + 1});
            if (node->left) stk.push({node->left, level + 1});
        }

        return res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations