Skip to content

Instantly share code, notes, and snippets.

@kennyxcao
Last active September 14, 2017 17:02
Show Gist options
  • Save kennyxcao/2b21c359d33e365ce9bb0c422c529714 to your computer and use it in GitHub Desktop.
Save kennyxcao/2b21c359d33e365ce9bb0c422c529714 to your computer and use it in GitHub Desktop.
var BinaryTree = function (value) {
this.value = value;
this.left = null;
this.right = null;
};
// Starting Level at root = 0
const findLargestLevel = function(node) {
var queue = [[node, 0]];
var levelSum = [];
var largestSum = -Infinity;
var largestLevel = 0;
while (queue.length > 0) {
var tuple = queue.shift();
var node = tuple[0];
var depth = tuple[1];
if (levelSum[depth] === undefined) {
levelSum.push(node.value);
} else {
levelSum[depth] += node.value;
}
if (node.left) {
queue.push([node.left, depth + 1]);
}
if (node.right) {
queue.push([node.right, depth + 1]);
}
}
for (var i = 0; i < levelSum.length; i++) {
if (levelSum[i] > largestSum) {
largestSum = levelSum[i];
largestLevel = i;
}
}
return largestLevel;
};
// --------- TEST 1 ------
// Largest level => 2
const myTree = new BinaryTree(10);
myTree.left = new BinaryTree(5);
myTree.right = new BinaryTree(15);
myTree.left.left = new BinaryTree(3);
myTree.left.right = new BinaryTree(8);
myTree.right.left = new BinaryTree(12);
myTree.right.right = new BinaryTree(20);
/*
10
5 15
3 8 12 20
*/
// --------- TEST 2 ------
// Same Value at level 1 and 2 => should return level 1
const myTree2 = new BinaryTree(10);
myTree2.left = new BinaryTree(5);
myTree2.right = new BinaryTree(30);
myTree2.left.left = new BinaryTree(5);
myTree2.left.right = new BinaryTree(10);
myTree2.right.left = new BinaryTree(15);
myTree2.right.right = new BinaryTree(5);
/*
10
5 15
5 10 15 5
*/
console.log(findLargestLevel(myTree)); // 2
console.log(findLargestLevel(myTree2)); // 1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment