root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: [3.00000,14.50000,11.00000] Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].
Example 2:
Input: root = [3,9,20,15,7] Output: [3.00000,14.50000,11.00000]
Constraints:
[1, 104].-231 <= Node.val <= 231 - 1This 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.
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.
C++
Java
Python
C#
JavaScript
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.
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.
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.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Using Queue | Time Complexity: |
| Depth-First Search (DFS) With Pre-order Traversal | Time Complexity: |
LeetCode 637. Average of Levels in Binary Tree (Algorithm Explained) • Nick White • 14,179 views views
Watch 9 more video solutions →Practice Average of Levels in Binary Tree with our built-in code editor and test cases.
Practice on FleetCode