Solution Explanation for LeetCode 515: Find Largest Value in Each Tree Row

This problem asks to find the largest value in each row of a binary tree. We can solve this using either Breadth-First Search (BFS) or Depth-First Search (DFS).

Approach 1: Breadth-First Search (BFS)

This approach uses a queue to process nodes level by level.

Algorithm:

1. Initialization: Create a queue q and add the root node to it. Initialize an empty list ans to store the largest values of each row.

2. Level Processing: While the queue is not empty:

   • Get the size size of the queue (number of nodes at the current level).
   • Initialize a variable maxVal to negative infinity.
   • Iterate size times:
     • Dequeue a node from the queue.
     • Update maxVal to the maximum of maxVal and the node's value.
     • Enqueue the node's left and right children if they exist.
   • Append maxVal to ans.

3. Return: Return ans.

Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited and processed exactly once.

Space Complexity: O(W), where W is the maximum width of the tree. In the worst case (a complete binary tree), W can be proportional to N. The queue stores nodes from at most one level at a time.

Approach 2: Depth-First Search (DFS)

This approach uses recursion to traverse the tree.

Algorithm:

1. Initialization: Create an empty list ans to store the largest values of each row.

2. Recursive Function dfs(root, level):

   • Base Case: If root is null, return.
   • If the current level is equal to the size of ans, it means we are encountering a new row, so append root.val to ans.
   • Otherwise, update the value at ans[level] with the maximum of the current value and root.val.
   • Recursively call dfs for the left and right children with level + 1.

3. Call dfs: Call dfs(root, 0) to start the traversal.

4. Return: Return ans.

Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited and processed exactly once.

Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be proportional to N.

Code Implementation (Python)

BFS:

from collections import deque
 
def largestValues(root):
    ans = []
    if not root:
        return ans
    q = deque([root])
    while q:
        size = len(q)
        max_val = float('-inf')
        for _ in range(size):
            node = q.popleft()
            max_val = max(max_val, node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        ans.append(max_val)
    return ans
 

DFS:

def largestValues_dfs(root):
    ans = []
    def dfs(node, level):
        if not node:
            return
        if level == len(ans):
            ans.append(node.val)
        else:
            ans[level] = max(ans[level], node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return ans
 

Both BFS and DFS provide efficient solutions to this problem, with similar time complexities. The choice between them might depend on factors like personal preference, memory constraints (BFS might be slightly better for very wide trees), or whether you need to traverse the tree in a specific order. The provided code snippets show implementations in Python; adapting them to other languages (Java, C++, Go, TypeScript, Rust) is straightforward, using the equivalent data structures (queues, lists, vectors, etc.).