Community

Start a Thread
Filters
By Category
Notifications
Subscribe You’re not receiving notifications from this thread.

Max Per Level (Main Thread)

Here is the interview question prompt, presented for reference.

Given a binary tree, write a method to return an array containing the largest (by value) node values at each level. In other words, we're looking for the max per level.

So for instance, given the following binary tree, we'd get [2, 7, 9] if the method grabbed the correct maxes.

/*
       2
      / \
     3   7
    / \   \  
   5   8   9 
*/

maxValPerLevel(root);
// [2, 7, 9]

Assuming the standard tree node definition of:

function Node(val) {
  this.val = val;
  this.left = this.right = null;
}

Can you fill it out via the following function signature?

function maxValPerLevel(root) {
  // if (!root) { return []; }

  return;
};

Constraints

  • The number of nodes in the given tree <= 100000
  • The nodes will always contain integer values between -1000000000 and 1000000000
  • Expected time complexity : O(n)
  • Expected space complexity : O(n)

You can see the full challenge with visuals at this link.

Challenges • Asked over 5 years ago by Anonymous

Jake from AlgoDaily Commented on Aug 09, 2019:

This is the main discussion thread generated for Max Per Level.

Anonymous Commented on Aug 09, 2019:

Couldn't we just traverse the right branch?

Jake from AlgoDaily Commented on Nov 28, 2019:

Hi,

There's no guarantee of node order in a binary tree, only for binary search trees. From this answer (https://stackoverflow.com/questions/6380231/difference-between-binary-tree-and-binary-search-tree):

Binary tree: Tree where each node has up to two leaves

SNIPPET
1
 / \
2   3

Binary search tree: Used for searching. A binary tree where the left child contains only nodes with values less than the parent node, and where the right child only contains nodes with values greater than or equal to the parent.

SNIPPET
2
 / \
1   3
Anonymous Commented on Dec 31, 2019:

Hi, there is bug in the challenge.
AssertionError: expected [ 5, 9, 10, 1 ] to deeply equal [ 5, 3, 2, 1 ]
AssertionError: expected [ 8, 9, 10, 1 ] to deeply equal [ 8, 9, 10 ]
I have correct answers, but the expected once are different than test cases.

My code:
const map = new Map();
function maxValPerLevel(root) {
addLevel(root, 0);
return [...map.values()];
}
function addLevel(node, level) {
if (!node || !node.val)
return false;
if(!map.get(level) || map.get(level) &lt; node.val)
map.set(level, node.val);
return addLevel(node.left, level+1) || addLevel(node.right, level+1);
}

Anonymous Commented on Jan 01, 2020:

[deleted]

Anonymous Commented on Jan 01, 2020:

[deleted]

Anonymous Commented on Jan 01, 2020:

[deleted]

Jake from AlgoDaily Commented on Jan 01, 2020:

Hi,

It's a scoping problem. You have const map = new Map(); as a global, which is affecting subsequent test cases. If you encapsulate it in the maxValPerLevel function like below, it'll pass:

SNIPPET
function maxValPerLevel(root) {
  const map = new Map();
  addLevel(root, 0, map);
  return [...map.values()];
}

function addLevel(node, level, map) {
  if (!node || !node.val) 
    return false;
  if(!map.get(level) || map.get(level) < node.val) 
     map.set(level, node.val);
  return addLevel(node.left, level+1, map) || addLevel(node.right, level+1, map);
}