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)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.