Find Largest Value In Each Tree Row - Leetcode Solution

Problem Statement:

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

Example:

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

Explanation:

The first row has the largest value 1.

The second row has the largest value among the nodes of 3 and 2, which is 3.

The third row has the largest value among the nodes of 5, 3, and 9, which is 9.

Solution:

The problem requires us to find the largest value in each tree row using breadth-first search algorithm. Thus, we can solve this problem efficiently using BFS algorithm. We will start by creating a queue to perform BFS on the given binary tree.

Step 1: Create an empty array to store the maximum value of each row.

Step 2: Create a queue and push the root node of the tree onto the queue.

Step 3: Start a while loop, the loop will run until the queue becomes empty. The while loop will perform the following operations in each iteration:

a) Initialize a variable max_val as negative infinity. This variable will help us keep track of the maximum value in each row.

b) Fetch the size of the queue using the function queue.size(). We will use the queue size to get the nodes of the current row.

c) Iterate over the nodes of the current row. We will remove the nodes from the queue, one by one, and check if the value of the node is greater than the current max_val variable. If the value of the node is greater than the current max_val variable, update max_val with the value of the node.

d) Push the children of the nodes on the queue.

Step 4: Append the value of max_val variable to the array created in step 1. As we have found the maximum value of the current row, we will append it to the array.

Step 5: Return the array created in step 1.

Pseudo code:

def largestValues(root): if root is None: return [] result = [] queue = [] queue.append(root) while queue: n = len(queue) max_val = float('-inf') for i in range(n): node = queue.pop(0) if node.val > max_val: max_val = node.val if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(max_val) return result

Time Complexity:

The solution has to visit all the nodes of the given binary tree Once in order to calculate the maximum value of each row using breadth-first search algorithm. Thus, the time complexity of the solution will be O(n), where n is the number of nodes in the given binary tree.

Space Complexity:

The space complexity of the solution will be O(m), where m is the maximum number of nodes on a level of the binary tree. This is because the maximum number of nodes that can be present on the queue will be equal to the nodes in the last level of the binary tree. Thus, in the worst case scenario, the space complexity of the solution will be O(n/2), where n is the number of nodes in the given binary tree.

1