#515

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Find Largest Value in Each Tree Row

Find the largest value in each row of a binary tree using depth-first or breadth-first search techniques.

tree depth first search breadth first search binary tree

Problem Statement

You are given the root of a binary tree. Your task is to return an array containing the largest value in each row of the tree, where rows are 0-indexed.

To solve this, you'll need to traverse the binary tree and find the largest value in each row, updating the largest value as you progress across the nodes of each level.

Examples

Example 1

Input: root = [1,3,2,5,3,null,9]

Output: [1,3,9]

Example details omitted.

Example 2

Input: root = [1,2,3]

Output: [1,3]

Example details omitted.

Constraints

The number of nodes in the tree will be in the range [0, 104].
-231 <= Node.val <= 231 - 1

Solution Approach

Breadth-First Search (BFS)

Perform a breadth-first traversal where you process each level of the tree. For each level, determine the maximum value of the nodes at that level, then store it in the result array.

Depth-First Search (DFS)

Use a depth-first traversal to explore each node, passing down the level information. Keep track of the largest value at each depth level and update the result array as you go deeper into the tree.

State Tracking

Whether using BFS or DFS, maintain a state (e.g., a list) to keep track of the largest value encountered at each depth level. This ensures that the maximum values for all levels are collected properly.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(h)

The time complexity is O(n) due to visiting each node exactly once during the traversal. The space complexity is O(h), where h is the height of the tree, as the maximum space used will be related to the height when storing nodes in memory during traversal.

What Interviewers Usually Probe

The candidate demonstrates familiarity with tree traversal techniques like DFS and BFS.
The candidate tracks row-wise maximum values accurately.
The candidate optimizes space usage during the tree traversal.

Common Pitfalls or Variants

Common pitfalls

Not handling edge cases, like empty trees or trees with only one node.
Confusing the traversal order, leading to incorrect row-wise maximums.
Failing to update the maximum value correctly across all rows.

Follow-up variants

Finding the second largest value in each row.
Handling trees that contain non-unique values within a row.
Optimizing for memory usage in sparse trees.

FAQ

How can I solve the Find Largest Value in Each Tree Row problem using BFS?

To solve it using BFS, process the nodes level by level, keeping track of the maximum value at each level and returning those as an array.

Can I use DFS to solve the Find Largest Value in Each Tree Row problem?

Yes, DFS can be used to traverse the tree, tracking the maximum value at each depth, and updating the result accordingly.

What is the time complexity of solving Find Largest Value in Each Tree Row?

The time complexity is O(n), where n is the number of nodes, because each node is visited once.

What are the common mistakes when solving this problem?

Common mistakes include not handling edge cases, incorrect traversal logic, or failure to track the largest value properly across rows.

How do I optimize space when solving Find Largest Value in Each Tree Row?

Space optimization can be achieved by using an iterative BFS or DFS approach, avoiding unnecessary data structures, and managing row-wise state efficiently.

terminal

Solution

Solution 1: BFS

We define a queue $q$ and put the root node into the queue. Each time, we take out all the nodes of the current level from the queue, find the maximum value, and then put all the nodes of the next level into the queue until the queue is empty.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

# 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]:
        ans = []
        if root is None:
            return ans
        q = deque([root])
        while q:
            x = -inf
            for _ in range(len(q)):
                node = q.popleft()
                x = max(x, node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(x)
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

# 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]:
        ans = []
        if root is None:
            return ans
        q = deque([root])
        while q:
            x = -inf
            for _ in range(len(q)):
                node = q.popleft()
                x = max(x, node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(x)
        return ans

Continue Practicing

#513 find bottom left tree value #530 minimum absolute difference in bst #449 serialize and deserialize bst