515. Find Largest Value in Each Tree Row


Problem Description

In this problem, we are provided with the root of a binary tree. Our task is to find the largest value in each row of the tree and return them in an array. The binary tree is not necessarily a binary search tree, which means that the tree is not guaranteed to follow the ordering property of binary search trees. Each row in the array corresponds to a level of the tree, indexed starting from 0. The first element of the array corresponds to the root level, and subsequent elements correspond to the succeeding levels of the tree.

Intuition

To solve this problem, a common approach is to perform a level order traversal of the binary tree. A level order traversal means that we visit all the nodes at the current level before moving on to the nodes of the next level.

Here is how we can proceed:

  1. Start with the root node by adding it to a queue. Since we only have the root, the largest value for the root level is the value of the root itself.

  2. While the queue is not empty, we will perform the following steps for each level:

    • Initialize a variable to keep track of the maximum value for the current level. Initially, it can be set to negative infinity to ensure that any node value will be larger.
    • Get the number of nodes in the current level (the size of the queue).
    • Iterate through these nodes and for each node:
      • Update the maximum value if the current node's value is greater.
      • Add the left and right children of the current node to the queue if they exist.
  3. After finishing the iteration for the current level, add the maximum value we found to the answer array.

  4. Repeat the process for the next level.

  5. Once the queue is empty, it means we have visited all levels and obtained the largest value for each level. The answer array is now complete, and we return it as the result.

This approach ensures that for each level, we are able to assess all the nodes, and identify the largest value, thereby constructing our array of the largest values for each level.

Solution Approach

The provided solution code implements the level order traversal approach to solve the problem. It uses the following algorithms, data structures, and patterns:

  1. Breadth-First Search (BFS): The level order traversal is a type of BFS, in which nodes are visited level by level from top to bottom. This traversal is suitable for finding the largest value in each row since it processes all nodes at each level before moving on to the next one.

  2. Queue Data Structure: The code utilizes a deque (double-ended queue) from Python's collections module to efficiently perform the BFS. A queue is ideal for BFS since it follows the First-In-First-Out (FIFO) principle, which ensures that nodes are processed in the order they are discovered.

  3. Looping through Levels: The algorithm uses a while loop to keep processing nodes as long as the queue is not empty. Inside this loop, there is another for loop that iterates over each node of the current level, which is determined by the current size of the queue.

  4. Tracking Maximum Values: The variable t is used to keep track of the maximum value for the current level. It's initially set to -inf (negative infinity) to ensure any node's value will be greater, and hence it can be updated as soon as a node with a value is encountered.

  5. Adding Children to Queue: While processing each node, the code checks whether the left or right child exists. If they do, these children are added to the queue for future processing. This step is crucial to expand the traversal to subsequent levels.

Here's a step-by-step breakdown of the code implementation:

1# The TreeNode structure is predefined; each node has a value and links to left and right children.
2class Solution:
3    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
4        if root is None:  # If the tree is empty, there are no values to process, return an empty list.
5            return []
6        q = deque([root])  # Initialize the deque with the root node to start the level order traversal.
7        ans = []  # This list will store the largest values for each level.
8      
9        # Continue the loop as long as there are nodes to process.
10        while q:  
11            t = -inf  # Set the maximum value for current level to negative infinity.
12          
13            # Process each node of the current level.
14            for _ in range(len(q)):  # 'for' loop runs for the number of nodes in the current level.
15                node = q.popleft()  # Dequeue the front node of the queue.
16                t = max(t, node.val)  # Update the maximum value if node's value is greater.
17              
18                # Enqueue children of the current node if they exist.
19                if node.left:
20                    q.append(node.left)
21                if node.right:
22                    q.append(node.right)
23          
24            # After processing the current level, the largest value is appended to the answer.
25            ans.append(t)
26      
27        # Return the array containing the largest values for each level.
28        return ans

This implementation ensures that the traversal continues as long as there are nodes left to be processed. The largest value for each level is determined by comparing it with the default minimum value of -inf, and updating it with the node's value if it's greater. By the end of the traversal, the ans list contains the largest values for each level, which is the desired output of the problem.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's consider a small binary tree as our example to illustrate the solution approach:

1        3
2       / \
3      1   5
4     /   / \
5    0   4   7

Now, let's walk through the solution step-by-step, applying the level order traversal approach described above.

  1. First, we initiate the traversal by adding the root node (which has the value 3) to a queue. Since this is the only node at level 0, the largest value for this level is 3.

  2. Now, we begin iterating level by level. Our queue currently contains the root:

    1Queue: [3]
  3. We remove the root node from the queue and inspect its children. Since the root node has two children, with values 1 and 5, we add these two nodes to the queue. The largest value at this level (level 0) is still 3, so we store 3 in our answer array.

    1Queue: [1, 5]
    2Answer: [3]
  4. For the next level (level 1), both nodes in the queue are processed. We start by setting the maximum value for this level to negative infinity:

    1t = -inf
  5. We dequeue the first node (with value 1) and compare it with our max value t. Since 1 is greater than -inf, t becomes 1. This node has a left child with value 0, which we enqueue:

    1Queue: [5, 0]
  6. The next node with value 5 is dequeued and compared with t. Since 5 is greater than 1, t becomes 5. This node has two children with values 4 and 7, which we enqueue:

    1Queue: [0, 4, 7]
  7. With all nodes at level 1 processed, we update our answer array with the maximum value found at this level, which is 5:

    1Answer: [3, 5]
  8. We repeat this process for the next level, iterating over the remaining nodes in the queue (0, 4, and 7). We'll find that 7 is the maximum value at this level (level 2).

  9. Our process continues until the queue is empty, which means we've processed all the levels and found the maximum value for each.

  10. Finally, we return the completed ans array as the result:

1Answer: [3, 5, 7]

This example demonstrates how the approach processes each level of the binary tree and finds the largest value for each level, completing the task successfully.

Python Solution

1from collections import deque
2from typing import List, Optional
3
4# Definition for a binary tree node.
5class TreeNode:
6    def __init__(self, val=0, left=None, right=None):
7        self.val = val
8        self.left = left
9        self.right = right
10
11class Solution:
12    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
13        """
14        Function to find the largest value in each level of a binary tree.
15
16        :param root: Optional[TreeNode] - root of the binary tree
17        :return: List[int] - a list containing the largest value of each level
18        """
19        # If the root is none, return an empty list as there are no levels in the tree.
20        if root is None:
21            return []
22      
23        # Initialize a queue for BFS traversal and a list to store the answers.
24        queue = deque([root])
25        largest_values = []
26
27        # Traverse the tree level by level.
28        while queue:
29            # Initialize the largest element of the current level to negative infinity.
30            max_value = float('-inf')
31            # Iterate over all nodes at the current level.
32            for _ in range(len(queue)):
33                node = queue.popleft()  # Get the next node from the queue.
34                max_value = max(max_value, node.val)  # Update the largest value found in this level.
35                # If left child exists, append it to the queue for the next level.
36                if node.left:
37                    queue.append(node.left)
38                # If right child exists, append it to the queue for the next level.
39                if node.right:
40                    queue.append(node.right)
41            # After visiting all nodes at the current level, add the largest value to the results list.
42            largest_values.append(max_value)
43
44        # Return the list of largest values, one from each level.
45        return largest_values
46

Java Solution

1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    int val;
6    TreeNode left;
7    TreeNode right;
8    TreeNode() {}
9    TreeNode(int val) { this.val = val; }
10    TreeNode(int val, TreeNode left, TreeNode right) {
11        this.val = val;
12        this.left = left;
13        this.right = right;
14    }
15}
16
17/**
18 * Class containing the method to find the largest values in each tree row.
19 */
20class Solution {
21    /**
22     * Finds the largest values in each row of a binary tree.
23     *
24     * @param root The root of the binary tree.
25     * @return A list of the largest values in each row of the tree.
26     */
27    public List<Integer> largestValues(TreeNode root) {
28        // List to store the largest values in each row.
29        List<Integer> largestValues = new ArrayList<>();
30      
31        // Return the empty list if the tree is empty.
32        if (root == null) {
33            return largestValues;
34        }
35      
36        // Queue to perform level order traversal
37        Deque<TreeNode> queue = new ArrayDeque<>();
38      
39        // Start the traversal with the root node.
40        queue.offer(root);
41      
42        // Loop until the queue is empty, indicating all levels have been visited.
43        while (!queue.isEmpty()) {
44            // Initialize the variable to store the max value for the current level.
45            int maxInLevel = queue.peek().val;
46          
47            // Traverse all nodes at this level.
48            for (int i = queue.size(); i > 0; --i) {
49                // Get the next node from the queue.
50                TreeNode node = queue.poll();
51              
52                // Update the max value with the max of current max and node's value.
53                maxInLevel = Math.max(maxInLevel, node.val);
54              
55                // Add the left child to the queue if it exists.
56                if (node.left != null) {
57                    queue.offer(node.left);
58                }
59              
60                // Add the right child to the queue if it exists.
61                if (node.right != null) {
62                    queue.offer(node.right);
63                }
64            }
65          
66            // After finishing the level, add the max value found to the result list.
67            largestValues.add(maxInLevel);
68        }
69      
70        // Return the list of maximum values found.
71        return largestValues;
72    }
73}
74

C++ Solution

1#include <vector>
2#include <queue>
3
4// Definition for a binary tree node.
5struct TreeNode {
6    int val;
7    TreeNode *left;
8    TreeNode *right;
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    // Method to find the largest value in each level of a binary tree
16    vector<int> largestValues(TreeNode* root) {
17        // If the tree is empty, return an empty vector
18        if (!root) return {};
19
20        // Queue for holding nodes to process
21        queue<TreeNode*> nodes_queue;
22        nodes_queue.push(root);
23
24        // Vector to store the largest values
25        vector<int> largest_values;
26
27        // Process nodes level by level
28        while (!nodes_queue.empty()) {
29            // Initialize the current level's largest value with the first node's value
30            int current_level_largest = nodes_queue.front()->val;
31
32            // Iterate through nodes in the current level
33            for (int i = nodes_queue.size(); i > 0; --i) {
34                // Get the next node in the queue
35                TreeNode* current_node = nodes_queue.front();
36                // Update the largest value if the current node is greater
37                current_level_largest = max(current_level_largest, current_node->val);
38                // Remove the processed node from the queue
39                nodes_queue.pop();
40                // Add child nodes of the current node to the queue for the next level
41                if (current_node->left) nodes_queue.push(current_node->left);
42                if (current_node->right) nodes_queue.push(current_node->right);
43            }
44
45            // Append the largest value for this level to the results
46            largest_values.push_back(current_level_largest);
47        }
48
49        return largest_values;
50    }
51};
52

Typescript Solution

1// The TreeNode class represents a node in a binary tree with a numeric value.
2class TreeNode {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6
7  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8    this.val = val === undefined ? 0 : val;
9    this.left = left === undefined ? null : left;
10    this.right = right === undefined ? null : right;
11  }
12}
13
14/**
15 * Finds the largest value in each level of a binary tree.
16 * @param {TreeNode | null} root - The root of the binary tree.
17 * @returns {number[]} An array containing the largest values from each level.
18 */
19function findLargestValues(root: TreeNode | null): number[] {
20  const largestValues: number[] = [];
21  const nodeQueue: TreeNode[] = [];
22
23  if (root) nodeQueue.push(root);
24
25  while (nodeQueue.length > 0) {
26    const queueLength = nodeQueue.length;
27    let levelMax = -Infinity;
28
29    for (let i = 0; i < queueLength; i++) {
30      const node = nodeQueue.shift(); // Retrieves and removes the head of the queue
31      if (node) {
32        levelMax = Math.max(levelMax, node.val);
33        if (node.left) nodeQueue.push(node.left);
34        if (node.right) nodeQueue.push(node.right);
35      }
36    }
37
38    largestValues.push(levelMax);
39  }
40
41  return largestValues;
42}
43

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O(n), where n is the number of nodes in the binary tree. This is because the code uses a breadth-first search (BFS) algorithm that visits each node exactly once to find the largest value in each level of the tree.

Space Complexity

The space complexity is also O(n). This is the worst-case scenario where the tree is extremely unbalanced, and all nodes are on a single side of the tree, leading to all nodes being held in the queue at one point in time. For a balanced tree, however, the largest space consumption would occur at the level with the most nodes, which is approximately n/2 nodes for a full binary tree at the last level, but it is still expressed as O(n) in Big O notation for simplicity as it remains proportional to the number of nodes.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫