# Find Largest Value in Each Tree Row
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-largest-value-in-each-tree-row)
Canonical: https://scaleengineer.com/dsa/problems/find-largest-value-in-each-tree-row
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin)
---
## Problem
Given the `root` of a binary tree, return _an array of the largest value in each row_ of the tree **(0-indexed)**.

**Example 1:**

![](https://assets.glich.co/dsa/find-largest-value-in-each-tree-row/image0.jpg) 

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

**Example 2:**

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

**Constraints:**

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

# Approaches
## Breadth-First Search (Level Order Traversal)
This approach traverses the tree level by level using a queue. For each level, it iterates through all the nodes at that level to find the maximum value, then adds it to the result list. This is a very intuitive method for problems involving tree levels.
**Time:** O(N), where N is the total number of nodes in the tree. Each node is visited, enqueued, and dequeued exactly once. · **Space:** O(W), where W is the maximum width of the tree. In the worst-case scenario of a complete binary tree, the width can be up to N/2, leading to a space complexity of O(N).
**Pros:** Very intuitive for level-by-level tree problems.; Iterative approach avoids recursion depth limits and potential stack overflow on very deep trees.
**Cons:** Can be less space-efficient than DFS for wide trees (e.g., complete binary trees), as the queue can hold up to O(N) nodes.
### Explanation
We can solve this problem by performing a level order traversal of the tree, which is naturally implemented using a Breadth-First Search (BFS) algorithm with a queue. 

The core idea is to process the tree one level at a time. We start by putting the root node in a queue. Then, we enter a loop that continues as long as the queue is not empty. In each iteration of this outer loop, we are processing a single level. We first determine the number of nodes on the current level by checking the queue's size. We then iterate exactly that many times, dequeueing one node at a time. While processing the nodes of a level, we keep track of the maximum value seen so far. After the inner loop finishes, we have the largest value for that level, which we add to our result list. We also add the children of each processed node to the queue, which sets up the next level for the subsequent iteration of the outer loop.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

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

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

            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                maxInLevel = Math.max(maxInLevel, currentNode.val);

                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
            result.add(maxInLevel);
        }

        return result;
    }
}
```
### Algorithm
- Initialize an empty list `result`.
- If the `root` is null, return the empty list.
- Create a `Queue` and add the `root` node.
- While the queue is not empty:
  - Get the number of nodes in the current level, `levelSize = queue.size()`.
  - Initialize a variable `maxInLevel` to `Integer.MIN_VALUE`.
  - Loop `levelSize` times:
    - Dequeue a node `currentNode`.
    - Update `maxInLevel` with the maximum of its current value and `currentNode.val`.
    - Enqueue the left and right children of `currentNode` if they are not null.
  - Add `maxInLevel` to the `result` list.
- Return `result`.

## Depth-First Search (Recursive)
This approach uses a recursive Depth-First Search (DFS) traversal. By passing the current level (or depth) as a parameter in the recursion, we can keep track of the maximum value for each level in a results list.
**Time:** O(N), where N is the total number of nodes. Each node is visited exactly once. · **Space:** O(H), where H is the height of the tree, due to the recursion call stack. In a balanced tree, this is O(log N), which is very efficient. In the worst case of a skewed tree, the height is N, leading to O(N) space complexity.
**Pros:** More space-efficient than BFS for many common tree structures, especially balanced or near-balanced trees (O(log N) vs O(N)).; The recursive implementation can be very concise and elegant.
**Cons:** May cause a stack overflow for extremely deep trees (e.g., a skewed tree with many nodes).; The logic might be slightly less direct for a level-based problem compared to BFS.
### Explanation
A DFS approach can also solve this problem elegantly. We can use a pre-order traversal (`Node -> Left -> Right`) and maintain the current `level` of the traversal. We use a list, let's call it `result`, to store the largest value for each level. The index of the list corresponds to the level number.

We define a recursive helper function, `dfs(node, level, result)`. When we visit a `node` at a given `level`, we check if this level is new. We can determine this by comparing the `level` with the current size of the `result` list. If `level` equals `result.size()`, it's the first time we've reached this depth, so we add the node's value to the `result` list. If `level` is less than `result.size()`, it means we've already visited a node at this level, so we simply update the existing maximum value at `result.get(level)` if the current node's value is greater. After processing the current node, we recursively call the function for its left and right children, incrementing the level by one.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    private void dfs(TreeNode node, int level, List<Integer> result) {
        if (node == null) {
            return;
        }

        // If this is the first time we are visiting this level
        if (level == result.size()) {
            result.add(node.val);
        } else {
            // We have seen this level before, so update the max value
            result.set(level, Math.max(result.get(level), node.val));
        }

        // Recurse for children at the next level
        dfs(node.left, level + 1, result);
        dfs(node.right, level + 1, result);
    }
}
```
### Algorithm
- Initialize an empty list `result`.
- Create a recursive helper function `dfs(node, level, result)`.
- Start the process by calling `dfs(root, 0, result)`.
- Inside the `dfs` function:
  - If the current `node` is null, return.
  - Check if the `level` is equal to the current size of the `result` list.
    - If yes, it's the first node at this level. Add `node.val` to `result`.
    - If no, a value for this level already exists. Update it with `Math.max(result.get(level), node.val)`.
  - Recursively call `dfs` for the left child with `level + 1`.
  - Recursively call `dfs` for the right child with `level + 1`.
- Finally, return the `result` list.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List < Integer > largestValues ( TreeNode root ) { List < Integer > ans = new ArrayList <>(); if ( root == null ) { return ans ; } Deque < TreeNode > q = new ArrayDeque <>(); q . offer ( root ); while (! q . isEmpty ()) { int t = q . peek (). val ; for ( int i = q . size (); i > 0 ; -- i ) { TreeNode node = q . poll (); t = Math . max ( t , node . val ); if ( node . left != null ) { q . offer ( node . left ); } if ( node . right != null ) { q . offer ( node . right ); } } ans . add ( t ); } return ans ; } }
```

### CPP

```cpp
/** * 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 {}; queue < TreeNode *> q { { root } }; vector < int > ans ; while ( ! q . empty ()) { int t = q . front () -> val ; for ( int i = q . size (); i ; -- i ) { TreeNode * node = q . front (); t = max ( t , node -> val ); q . pop (); if ( node -> left ) q . push ( node -> left ); if ( node -> right ) q . push ( node -> right ); } ans . push_back ( t ); } return ans ; } };
```

### Python

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