Problem

Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

Examples

Example 1:

 graph TD;
     A[1]
     B[3]
     C[2]
     D[5]
     E[3]
     F[9]
 
     A --> B & C
     B --> D & E
     C ~~~ N1:::hidden
     C --> F

classDef hidden display: none;
classDef highest fill:#ADD8E6,stroke:#0000FF,stroke-width:2px; class A,B,F highest;
  
1
2

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

Example 2:

1
2

Input: root = [1,2,3]
Output: [1,3]

Solution

Method 1 - Level order traversal

We need to find the largest value in each row of a binary tree. This problem can be efficiently solved using Breadth-First Search (BFS) traversal. In BFS, we traverse the tree level-by-level which is perfect for this problem as we need to consider each row separately.

Here are the steps:

  1. Initialize an empty list ans to store the largest values.
  2. Use a queue (FIFO) to help with the BFS traversal.
  3. Start by adding the root node to the queue.
  4. While the queue is not empty:
    • Determine the number of nodes at the current level (using the queue size).
    • Iterate over all nodes at this level, keeping track of the largest value.
    • Add the children of the current node to the queue for the next level.
    • After finishing the current level, append the largest value to ans.
  5. Return the list ans.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 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

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
	        return ans;
	    }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            int maxValue = Integer.MIN_VALUE;

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.val > maxValue) {
                    maxValue = node.val;
                }
                if (node.left != null) {
	                queue.add(node.left);
	            }
                if (node.right != null) {
	                queue.add(node.right);
	            }
            }
            ans.add(maxValue);
        }
        return ans;
    }
}
 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

class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        from collections import deque
        ans = []
        if not root:
            return ans
        
        queue = deque([root])
        
        while queue:
            size = len(queue)
            max_value = float('-inf')
            
            for _ in range(size):
                node = queue.popleft()
                if node.val > max_value:
                    max_value = node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                    
            ans.append(max_value)
        
        return ans

Complexity

  • ⏰ Time complexity: O(n) as we visit each node exactly once, where n is the number of nodes in the tree.
  • 🧺 Space complexity: O(n), as the maximum number of nodes that can be held in the queue at any given time is the width of the tree, which is m in the worst case.