The Largest Value of Each Row of a Binary Tree

Given a binary tree, find the max value of each level of a Binary Tree.

The high level approach to solving this problem involves traversing the tree using one of the three common traversal techniques: pre-order, in-order, or post-order. The depth of each node is tracked during traversal, with the root node being the 0th level. Lastly, a map that associates depth with the maximum value encountered at that level is maintained.

Starting at the root, the algorithm checks if the depth of the current node exists as a key in the map. If the current depth does not exist as a key in the map, it means that the current level has not been processed yet. In this case, map the current node's value to its depth, indicating that it's the maximum value seen at that level. If the map already contains the current depth as a key, compare the maximum value seen so far for that level with the value of the current node. If the current node's value is greater, update the map's value for that depth to reflect the new maximum. Once the current node has been processed, continue to traverse to the left and right subtrees and repeat the process.

const maxPerRow = (root) => {
  const maxPerRow = {};
  maxPerRow(root, maxPerRow, 0);
  return maxPerRow;
}

const maxPerRow = (root, maxPerRow, depth) => {
  if (!root)
    return;

  if (!maxPerRow[depth])
    maxPerRow[depth] = root.val;
  else
    maxPerRow[depth] = Math.max(maxPerRow[depth], root.val);

  maxPerRow(root.left, maxPerRow, depth + 1);
  maxPerRow(root.right, maxPerRow, depth + 1);
}

The time complexity for this problem is O(n) because all nodes are processed. The space complexity for this problem depends on the shape of the tree. If the tree is relatively balanced, then the space complexity is close to O(log(n)). If the tree is extremely skewed, then the space complexity is closer to O(n).