# Deepest Leaves Sum — Asked in Microsoft, Adobe and Expedia Interview

# Problem Statement :

You have been given a binary tree of integers. Your task is to calculate the sum of all the leaf nodes which are present at the deepest level of this binary tree. If there are no such nodes, print 0.

NOTE: The deepest level of a binary tree is the level which is present at the maximum depth from the root node.

**Input:**

`71 2 16 110 -1 -1 5 -1 -1 -1 -1`

**Output:**

`115`

# Approach :

# Level Order Traversal

The idea is to perform a level order traversal of the given binary tree from the root node. The nodes which are present at the deepest level will be processed last as we are processing the tree level by level.

Here is the complete algorithm-

Time Complexity — O(N)

Space Complexity — O(N)