Deepest Leaves Sum Java Solution

Deepest Leaves Sum Java Solution

  May 03, 2022    

---

Problem:

Given the root of a binary tree, return the sum of values of its deepest leaves.

 

Solution:

 Idea is to use BFS/ Level order Traversal

public int deepestLeavesSum(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        int curSum = 0;
        int maxSum = Integer.MIN_VALUE;
        q.add(root);
        q.add(null);
        while(!q.isEmpty()) {
            TreeNode node = q.poll();
            if(node == null) {
                maxSum = curSum;
                curSum = 0;
                if(q.isEmpty()) break;
                q.add(null);
                continue;
            }
            curSum+=node.val;
            if(node.left!=null)
            q.add(node.left);
            if(node.right!=null)
            q.add(node.right);
        }
        return maxSum;
    }