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.