Sponsored
Sponsored
This approach uses a Breadth-First Search (BFS) strategy to traverse the binary tree level by level. For each level, we calculate the sum of node values and the count of nodes, then compute the average for each level. The BFS technique helps in handling each level independently using a queue.
Time Complexity: O(N), where N is the number of nodes in the tree, as each node is processed once.
Space Complexity: O(M), where M is the maximum number of nodes at any level, corresponding to the queue holding these nodes.
In this C solution, we implement the BFS traversal using a queue. We enqueue the root node first, then for each node, enqueue its children. The sum and count for each level are calculated, and averages are printed. This method ensures that each level is fully processed before the next begins.
This approach makes use of Depth-First Search (DFS) combined with pre-order traversal. The key idea is to traverse the tree, keeping track of the sum of node values and the count of nodes at each level. Recursive traversal helps gather the necessary values efficiently for averaging.
Time Complexity: O(N), where N signifies the number of tree nodes.
Space Complexity: O(H), where H is the height of the tree due to recursion stack.
1#include <stdio.h>
2#include <stdlib.h>
3#include <math.h>
4
5struct TreeNode {
6 int val;
7 struct TreeNode *left;
8 struct TreeNode *right;
9};
10
11void dfs(struct TreeNode* node, int level, double* level_sums, int* level_counts, int* max_level) {
12 if (!node) return;
13 if (level > *max_level) {
14 (*max_level)++;
15 level_sums[level] = node->val;
16 level_counts[level] = 1;
17 } else {
18 level_sums[level] += node->val;
19 level_counts[level]++;
20 }
21 dfs(node->left, level + 1, level_sums, level_counts, max_level);
22 dfs(node->right, level + 1, level_sums, level_counts, max_level);
23}
24
25void averageOfLevels(struct TreeNode* root) {
26 double level_sums[10000] = {0};
27 int level_counts[10000] = {0};
28 int max_level = -1;
29 dfs(root, 0, level_sums, level_counts, &max_level);
30 for (int i = 0; i <= max_level; ++i) {
31 printf("%.5f ", level_sums[i] / level_counts[i]);
32 }
33}
34
35int main() {
36 /* Create Binary tree with nodes */
37 struct TreeNode a, b, c, d, e;
38 a.val = 3; a.left = &b; a.right = &c;
39 b.val = 9; b.left = NULL; b.right = NULL;
40 c.val = 20; c.left = &d; c.right = &e;
41 d.val = 15; d.left = NULL; d.right = NULL;
42 e.val = 7; e.left = NULL; e.right = NULL;
43
44 averageOfLevels(&a);
45 return 0;
46}This C solution employs a depth-first approach that recursively calculates level sums and counts. The dfs function updates these for each node, with results computed for levels in the end.