Prerequisites: Binary trees, Binary tree traversal.
Problem: Given a binary tree, find the sum of leaves at deepest level.
Solution Approach: A simple preorder traversal can be used to solve this problem. This idea is to visit the tree downwards while keeping track of level, maxlevel and sum_at_deepest_level. Whenever we find a level deeper than current maxlevel, we update the sum_at_deepest_level with node value at this level otherwise if the current level is equal to maxlevel, we add the current node’s value to sum_at_deepest_level.
Finally, sum_at_deepest_level will have a sum of nodes’ values which are at the deepest level.
Time Complexity: O(N) as we need to explore each node at least once.
Space complexity: O(1), as we don’t need any significant extra space.