515. Find Largest Value in Tree Row - Explanation

Problem Link

1. Breadth First Search

Intuition

To find the largest value in each row, we need to visit all nodes level by level. BFS naturally processes nodes in level order using a queue. For each level, we track the maximum value seen among all nodes at that depth.

Algorithm

1. If the root is null, return an empty list.
2. Initialize a queue with the root node and an empty result list.
3. While the queue is not empty:
   • Record the number of nodes at the current level.
   • Initialize rowMax with the first node's value.
   • Process all nodes at this level: dequeue each node, update rowMax if needed, and enqueue its children.
   • Append rowMax to the result list.
4. Return the result list.

# 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 = []
        q = deque([root])
        while q:
            row_max = q[0].val
            for _ in range(len(q)):
                node = q.popleft()
                row_max = max(row_max, node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(row_max)

        return res

Time & Space Complexity

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

---

2. Depth First Search

Intuition

We can also solve this with DFS by tracking the current depth as we traverse. When we reach a node, if it's the first node at that depth, we add it to the result. Otherwise, we compare it with the existing maximum for that depth and update if necessary.

Algorithm

1. Initialize an empty result list.
2. Define a recursive DFS function that takes a node and its level:
   • If the node is null, return.
   • If level equals the size of the result list, append the node's value (first node at this depth).
   • Otherwise, update res[level] to be the maximum of its current value and the node's value.
   • Recursively call DFS on the left and right children with level + 1.
3. Call DFS starting from the root at level 0.
4. Return the result list.

# 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 = []
        def dfs(node, level):
            if not node:
                return
            if level == len(res):
                res.append(node.val)
            else:
                res[level] = max(res[level], node.val)

            dfs(node.left, level + 1)
            dfs(node.right, level + 1)

        dfs(root, 0)
        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$ for recursion stack.

---

3. Iterative DFS

Intuition

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.

Algorithm

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.

# 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

Time & Space Complexity

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

---

Common Pitfalls

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.