Sponsored
Sponsored
The BFS approach is well-suited for problems involving levels of a binary tree. We will use a queue to process the tree level by level, keeping track of the sum of node values at each level. We will maintain a variable to store the maximum sum encountered and the level corresponding to this maximum sum. By processing level by level, we ensure that when we find a new maximum, it is the smallest level with that sum.
Time Complexity: O(n), where n is the number of nodes in the tree, because each node is enqueued and dequeued exactly once.
Space Complexity: O(m), where m is the maximum number of nodes at any level in the tree, due to the queue holding nodes of a single level.
1#include <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4
5// Definition for a binary tree node.
6struct TreeNode {
7 int val;
8 struct TreeNode *left;
9 struct TreeNode *right;
10};
11
12// Queue Node
13typedef struct QueueNode {
14 struct TreeNode* treeNode;
15 struct QueueNode* next;
16} QueueNode;
17
18// Queue
19typedef struct {
20 QueueNode *front, *rear;
21} Queue;
22
23Queue* createQueue() {
24 Queue* q = (Queue*)malloc(sizeof(Queue));
25 q->front = q->rear = NULL;
26 return q;
27}
28
29void enQueue(Queue* q, struct TreeNode *node) {
30 QueueNode* temp = (QueueNode*)malloc(sizeof(QueueNode));
31 temp->treeNode = node;
32 temp->next = NULL;
33 if (q->rear == NULL) {
34 q->front = q->rear = temp;
35 return;
36 }
37 q->rear->next = temp;
38 q->rear = temp;
39}
40
41struct TreeNode* deQueue(Queue* q) {
42 if (q->front == NULL)
43 return NULL;
44 QueueNode* temp = q->front;
45 q->front = q->front->next;
46 if (q->front == NULL)
47 q->rear = NULL;
48 struct TreeNode* node = temp->treeNode;
49 free(temp);
50 return node;
51}
52
53int maxLevelSum(struct TreeNode* root) {
54 if (!root) return 0;
55
56 Queue* q = createQueue();
57 enQueue(q, root);
58 int maxSum = INT_MIN, level = 0, maxLevel = 0;
59
60 while (1) {
61 int levelSize = 0, levelSum = 0;
62 QueueNode* temp = q->front;
63
64 // Calculate the size of the current level
65 while (temp) {
66 levelSize++;
67 temp = temp->next;
68 }
69
70 if (levelSize == 0) break;
71
72 level++;
73 while (levelSize--) {
74 struct TreeNode* node = deQueue(q);
75 levelSum += node->val;
76 if (node->left) enQueue(q, node->left);
77 if (node->right) enQueue(q, node->right);
78 }
79
80 if (levelSum > maxSum) {
81 maxSum = levelSum;
82 maxLevel = level;
83 }
84 }
85 return maxLevel;
86}
87This implementation uses a queue to traverse the binary tree level by level. For each level, we calculate the sum of its node values. If this sum is greater than the previously recorded maximum sum, we update the maximum sum and note the level number. The queue helps ensure that each node of a given level is processed before nodes of the next level, which is key to implementing BFS.
This approach involves using a DFS traversal to explore the tree. We pass the current depth as a parameter to each recursive call and maintain an array or dictionary to track the sum of values at each level. After the traversal, we determine which level has the highest sum. DFS allows us to explore the tree deeply, and since each call carries a depth count, we can easily track levels.
Time Complexity: O(n)
Space Complexity: O(d), where d is the maximum depth of the tree (related to recursion stack depth and level count in the dictionary).
1from collections import defaultdict
2
3# Definition for a binary tree node.
4class TreeNode
The Python solution uses DFS by recursively traversing the tree and tracking the sum of node values at each level using a dictionary. After completing the traversal, it identifies the level with the maximum sum.