Problem Explanation:

Given a binary tree, you are asked to solve for the largest value in each row of the said tree.

Let's walk through an example:

1
2
3Input:
4
5          1
6         / \
7        3   2
8       / \   \
9      5   3   9
10
11Output: [1, 3, 9]

This is how it works:

• The first row only has 1, so 1 is the largest value.

• In the second row, it has values 3 and 2. Among these, 3 is the largest.

• In the third row, it has values 5, 3, and 9. Among these three, 9 is the largest.

Hence the output is [1, 3, 9].

Approach Explanation:

We will be using Breadth-First Search (BFS) to solve this problem.

We make use of a queue data structure, which helps us in performing the BFS.

We start by adding the root node to the queue. While the queue is not empty, we note down the number of nodes at the current level, sz, and find the maximum among all these nodes.

We then remove sz nodes from the front of the queue and add their respective children to the queue. For each of the nodes removed from the queue, we compare it with maxi, where maxi is used to store the maximum element in the current level.

Finally, we update maxi at each step when removing elements from the queue and add it to the ans list which is returned.

Solution

Consider that TreeNode is a structure/class which has the following three properties:

1. val: an integer variable which holds the value of the node.
2. left: a pointer to the left child of the node (TreeNode-type).
3. right: a pointer to the right child of the node (TreeNode-type).

Python Solution:

1
2Python
3class Solution:
4    def largestValues(self, root):
5        if not root:
6            return []
7
8        ans = []
9        q = collections.deque([root])
10
11        while q:
12            maxi = float('-inf')
13            for _ in range(len(q)):
14                node = q.popleft()
15                maxi = max(maxi, node.val)
16                if node.left:
17                    q.append(node.left)
18                if node.right:
19                    q.append(node.right)
20            ans.append(maxi)
21
22        return ans

Java Solution:

1
2Java
3public class Solution {
4  public List<Integer> largestValues(TreeNode root) {
5    if (root == null)
6      return new ArrayList<>();
7
8    List<Integer> ans = new ArrayList<>();
9    Deque<TreeNode> q = new ArrayDeque<>();
10    q.offer(root);
11
12    while (!q.isEmpty()) {
13      int size = q.size();
14      int maxi = Integer.MIN_VALUE;
15      for (int i = 0; i < size; i++) {
16        TreeNode node = q.poll();
17        maxi = Math.max(maxi, node.val);
18        if (node.left != null)
19          q.offer(node.left);
20        if (node.right != null)
21          q.offer(node.right);
22      }
23      ans.add(maxi);
24    }
25
26    return ans;
27  }
28}

Javascript Solution:

1
2Javascript
3var largestValues = function(root) {
4  if (!root) return [];
5
6  const q = [root];
7  const ans = [];
8  while (q.length !== 0) {
9    const sz = q.length;
10    let maxi = Number.MIN_SAFE_INTEGER;
11    for (let i = 0; i < sz; i++) {
12      const node = q.shift();
13      maxi = Math.max(maxi, node.val);
14      if (node.left) q.push(node.left);
15      if (node.right) q.push(node.right);
16    }
17    ans.push(maxi);
18  }
19  return ans;
20};

C++ Solution:

1
2C++
3class Solution {
4public:
5  vector<int> largestValues(TreeNode* root) {
6    if (root == nullptr)
7      return {};
8
9    vector<int> ans;
10    queue<TreeNode*> q{{root}};
11
12    while (!q.empty()) {
13      int maxi = INT_MIN;
14      for (int sz = q.size(); sz > 0; --sz) {
15        TreeNode* node = q.front();
16        q.pop();
17        maxi = max(maxi, node->val);
18        if (node->left)
19          q.push(node->left);
20        if (node->right)
21          q.push(node->right);
22      }
23      ans.push_back(maxi);
24    }
25
26    return ans;
27  }
28};

C# Solution:

1
2Csharp
3public class Solution {
4    public IList<int> LargestValues(TreeNode root) {
5        if (root == null)
6            return new List<int>();
7
8        IList<int> ans = new List<int>();
9        Queue<TreeNode> q = new Queue<TreeNode>();
10        q.Enqueue(root);
11
12        while (q.Count > 0) {
13            int sz = q.Count;
14            int maxi = int.MinValue;
15            for (int i = 0; i < sz; i++) {
16                TreeNode node = q.Dequeue();
17                maxi = Math.Max(maxi, node.val);
18                if (node.left != null)
19                    q.Enqueue(node.left);
20                if (node.right != null)
21                    q.Enqueue(node.right);
22            }
23            ans.Add(maxi);
24        }
25
26        return ans;
27    }
28}

Swift Solution:

1
2Swift
3class Solution {
4    func largestValues(_ root: TreeNode?) -> [Int] {
5        guard let root = root else { return [] }
6        var result = [Int]()
7        var queue = [root]
8        while queue.count > 0 {
9            let size = queue.count
10            var maximum = Int.min 
11            for _ in 0 ..< size {
12                let node = queue.removeFirst()
13                maximum = max(maximum, node.val)
14                if let left = node.left {
15                    queue.append(left)
16                }
17                if let right = node.right {
18                    queue.append(right)
19                }
20            }
21            result.append(maximum)
22        }
23        return result
24    }
25}

Ruby Solution:

1
2Ruby
3def largest_values(root)
4  return [] if root.nil?
5  ans = []
6  queue = [root]
7  while !queue.empty? do
8    max_value = -1.0 / 0
9    size = queue.size
10    size.times do 
11      node = queue.shift 
12      max_value = [max_value, node.val].max 
13      queue << node.left if node.left
14      queue << node.right if node.right
15    end
16    ans << max_value
17  end
18  ans
19end

Kotlin Solution:

1
2kotlin
3fun largestValues(root: TreeNode?): List<Int> {
4    val results = mutableListOf<Int>()
5    if (root != null) {
6        val queue: Queue<TreeNode> = LinkedList()
7        queue.offer(root)
8        while (!queue.isEmpty()) {
9            val size = queue.size
10            var max = Int.MIN_VALUE
11            for (i in 0 until size) {
12                val node = queue.poll()
13                max = Math.max(max, node.`val`)
14                node.left?.let(queue::offer)
15                node.right?.let(queue::offer)
16            }
17            results.add(max)
18        }
19    }
20    return results
21}

Conclusion:

Takeaways from this problem might be to remember the technique of Breadth-First Search (BFS) using a queue and also going level by level and keeping a check of maximum element. Remembering such common patterns can often be useful in solving other similar problems. Total time complexity for above implementations in all the languages is linear in terms of the number of nodes in the tree since we are visiting each node only once, or O(N). The space complexity is also linear since we are using a queue data structure to hold the nodes, or O(N).