Find Largest Value in Each Tree Row

Hi Geeks! Welcome to 100 Days of Leetcode Challenge. In this article, you going to see about Find Largest Value in Each Tree Row.

Day 30

You need to find the largest value in each row of a binary tree.

Example:

Input: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

Output: [1, 3, 9]

Solution – Easy to understand

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public IList<int> LargestValues(TreeNode root) {
        var list = new List<int>();
        
        if(root == null)
            return list;
        Queue<TreeNode> q = new Queue<TreeNode>();
        q.Enqueue(root);
        
        while(q.Count > 0)
        {
            int size = q.Count;
            int max = int.MinValue;
            for(int i=0;i<size;i++)
            {
                TreeNode node = q.Dequeue();
                max = Math.Max(max,node.val);
                if(node.left != null)
                    q.Enqueue(node.left);
                if(node.right != null)
                    q.Enqueue(node.right);
            }
            list.Add(max);
        }
        return list;
    }
}

Time Complexity: O(n)

Space Complexity: O(1)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s