Deepest leaves sum of binary tree

Given a binary tree, find the sum of it deepest leaves and return it.

Example

Input:
       1
     /   \
    /     \
   2       3
          /  \
         /    \
        5      6
      /  \
     /    \
    7      8

Output:
15
// 7 and 8 are its deepest level leaves

Deepest leaves sum of binary tree.

As mentioned in the problem statement that we have to find all sum of all the leaves at the deepest level, the best way to get the leaves are by performing level order traversal on it.

Conceptually this is how it works,

• Perform the level order traversal on tree and store the nodes of each level in an 2d array.
• Store it reverse order such that the deepest level leaves are stored at the first index and then return their sum.

const deepestLeavesSum = (root) => {
  //get height of tree
  const h = height(root);
  
  //to store the tree values at each node
  const arr = [];
  
  //perform level order traversal
  levelOrderTraversal(root, h - 1, arr);
  
  //return the sum of deepest levels leaves
  return arr[0].reduce((a, b) => a + b);
};

//level order traversal
const levelOrderTraversal = (root, level, arr) => {
    //base: out of level
    if(level === -1){
        return;
    }
    
    //base: if no node return
    if(!root){
       return; 
    }
    
    //store the each level nodes at same level
    let val = arr[level] || [];
    arr[level] = [...val, root.val];
    
    //traverse left subtree
    levelOrderTraversal(root.left, level - 1, arr);
  
    //traverse right subtree
    levelOrderTraversal(root.right, level - 1, arr);
}

//height of tree
const height = (root) => {
    //if no node return 0;
    if(!root){
        return 0;
    }
    
    //return the max of left and right subtree
    return Math.max(height(root.left), height(root.right)) + 1;
}

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

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.right = new Node(6);
root.left.left.left = new Node(7);
root.right.right.right = new Node(8);

console.log(deepestLeavesSum(root));

Output:
15

Time complexity: O(n).
Space complexity: O(h * n).
Where h is the height of tree and n is the number of nodes in it.