🔍 Find Maximum Level Sum in a Binary Tree using BFS & DFS | Python Solution

Описание: 🌳 Find the Level with Maximum Sum in a Binary Tree | Python Solution 🚀

In this problem, we are given the root of a binary tree, and our task is to find the level with the maximum sum of node values. The level of the root is 1, its children are at level 2, their children are at level 3, and so on.

🔹 Understanding the Problem Statement:

We need to traverse all levels of the tree and calculate the sum of values at each level.
The level with the highest sum should be returned as the output.
If multiple levels have the same maximum sum, we return the smallest level (closest to the root).

✅ Approach: BFS (Breadth-First Search) - Level Order Traversal

Since we need to process the tree level by level, BFS (using a queue) is the best method.

🛠 Steps to Solve Using BFS:

1️⃣ Initialize a queue (deque) to store nodes for level-order traversal.
2️⃣ Keep track of the current level and the sum of node values at each level.
3️⃣ Traverse the tree using a loop, processing all nodes level by level.
4️⃣ Compare sums and update the maximum sum and corresponding level.
5️⃣ Return the level with the highest sum.

💻 Python Code (BFS Solution)

from collections import deque

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

class Solution:
def maxLevelSum(self, root):
if not root:
return 0

queue = deque([root])
max_sum = float('-inf')
min_level = 1
level = 1

while queue:
level_size = len(queue)
level_sum = 0

for _ in range(level_size):
node = queue.popleft()
level_sum += node.val

if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)

Update max sum and level if needed
if level_sum v max_sum:
max_sum = level_sum
min_level = level

level += 1 # Move to the next level

return min_level

📝 Explanation of BFS Solution

We use a queue (deque) to process the tree in level order.
At each level, we calculate the sum of all node values.
If the sum is greater than the previous max sum, we update the max sum and store the level number.

The smallest level with the highest sum is returned.

⏳ Time & Space Complexity Analysis

✅ Time Complexity: O(N) → We visit each node once.
✅ Space Complexity: O(D) → The queue holds at most D nodes (tree width).

🔄 Alternative Approach: DFS (Depth-First Search)

Instead of BFS, we can use DFS recursion to calculate the sum at each level.

💻 Python Code (DFS Solution)

class Solution:
def maxLevelSum(self, root):
level_sum = {}

def dfs(node, level):
if not node:
return
level_sum[level] = level_sum.get(level, 0) + node.val
dfs(node.left, level + 1)
dfs(node.right, level + 1)

dfs(root, 1)

Find the level with maximum sum
return min(level_sum, key=lambda x: (-level_sum[x], x))

📌 Explanation of DFS Solution

We use recursive DFS to traverse the tree.
A dictionary (level_sum) stores the sum at each level.
We return the smallest level with the highest sum.

🆚 BFS vs. DFS Comparison

Approach Time Complexity Space Complexity Best Use Case
BFS (Level Order) O(N) O(D) (Max width) Best for iterative traversal
DFS (Recursive) O(N) O(H) (Max depth) Best for recursive solutions

🔹 Example Walkthrough

Example 1

Input:

1
/ \
7 0
/ \
7 -8

Calculations:

Level 1 sum = 1
Level 2 sum = 7 + 0 = 7
Level 3 sum = 7 + (-8) = -1 📌 Output: 2 (Level with highest sum)

Example 2

Input:

989
\
10250
/ \
98693 -89388
\
-32127

Calculations:

Level 1 sum = 989
Level 2 sum = 10250
Level 3 sum = 98693 + (-89388) = 9305
Level 4 sum = -32127 📌 Output: 2 (Maximum sum at level 2)

🔥 Key Takeaways

✅ BFS is the best approach for level-order traversal problems.
✅ DFS provides an alternative recursive approach with slightly different memory usage.
✅ Time Complexity: O(N) (Both BFS & DFS).
✅ Space Complexity: O(D) (BFS) & O(H) (DFS).
✅ Understanding BFS and DFS is crucial for binary tree problems in coding interviews!

🚀 Master this problem to enhance your BFS & DFS skills! 🚀

#Python #LeetCode #BinaryTree #TreeTraversal #BFS #DFS #DataStructures #Algorithms #LeetCode75 #CodingInterview