DDSA Solutions

515. Find Largest Value in Each Tree Row

MediumView on LeetCode
TreeDepth-First SearchBreadth-First SearchBinary Tree
Time: O(n)
Space: O(n)

Problem Overview

Each tree row is a BFS level.

Intuition

Each tree row is a BFS level. Level-order traversal visits nodes left-to-right, top-to-bottom — so grouping by depth naturally yields one row per level. Track the maximum value seen while processing each level before moving to the next.

Algorithm

  1. 1If root is null, return empty list.
  2. 2BFS queue starting with root.
  3. 3For each level: snapshot queue size, initialize rowMax to negative infinity.
  4. 4Dequeue exactly that many nodes; update rowMax with each value; enqueue non-null children.
  5. 5Append rowMax to result after finishing the level.

Example Walkthrough

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

  1. 1.Level 0: nodes [1] -> max = 1.
  2. 2.Level 1: nodes [3,2] -> max = 3.
  3. 3.Level 2: nodes [5,3,9] -> max = 9.

Output: [1, 3, 9]

Common Pitfalls

  • •Initialize row max to Integer.MIN_VALUE — node values can be negative.
  • •Snapshot queue size before the inner loop; dequeuing changes the count mid-level.
  • •Do not mix nodes from different depths in one iteration.
515.cs
C#
// Approach: BFS level-order traversal; track the maximum value encountered
// across all nodes at each level.
// Time: O(n) Space: O(n)

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution
{
    public IList<int> LargestValues(TreeNode root)
    {
        if (root == null)
            return new List<int>();

        List<int> ans = new List<int>();
        Queue<TreeNode> q = new Queue<TreeNode>();
        q.Enqueue(root);

        while (q.Count > 0)
        {
            int mx = int.MinValue;
            int sz = q.Count;
            for (int i = 0; i < sz; i++)
            {
                TreeNode node = q.Dequeue();
                mx = Math.Max(mx, node.val);
                if (node.left != null)
                    q.Enqueue(node.left);
                if (node.right != null)
                    q.Enqueue(node.right);
            }
            ans.Add(mx);
        }

        return ans;
    }
}
Was this solution helpful?

Related Problems