By Long Luo

Here shows 2 approaches to slove this problem: BFS(Level Order Travesal) and DFS(Get Max Depth, then Traversal).

# BFS

To traverse the tree level by level, we generally use breadth first search. You can refer to this article Traverse the Tree Level by Level: Standard BFS Solution .

## Analysis

• Time Complexity: $O(n)$.
• Space Complexity: $O(n)$.

# DFS

1. Traverse the tree to find the max depth.
2. Traverse the tree again to compute the sum required.

## Analysis

• Time Complexity: $O(n)$.
• Space Complexity: $O(maxHeight)$.

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗