#637

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Average of Levels in Binary Tree

Calculate the average value of nodes on each level of a binary tree using traversal and state tracking.

tree depth first search breadth first search binary tree

Problem Statement

Given the root of a binary tree, return the average value of the nodes on each level of the tree. The root node is at level 0, and all its children are at level 1, and so on. You need to compute the average of node values at each level and return them as a list of floating-point numbers.

For example, given the root = [3,9,20,null,null,15,7], the output should be [3.00000,14.50000,11.00000]. At level 0, the average is 3, at level 1 it is 14.5, and at level 2 it is 11.

Examples

Example 1

Input: root = [3,9,20,null,null,15,7]

Output: [3.00000,14.50000,11.00000]

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]

Example details omitted.

Constraints

The number of nodes in the tree is in the range [1, 104].
-231 <= Node.val <= 231 - 1

Solution Approach

Level Order Traversal (BFS)

Perform a breadth-first traversal (BFS) to traverse each level of the tree. For each level, calculate the sum of the node values and divide it by the number of nodes at that level to find the average. This approach ensures that each level is processed in the correct order.

Depth-First Traversal (DFS)

Use a depth-first traversal (DFS) to visit each node and record the sum and count of nodes at each level. After the traversal, compute the averages using the recorded values. This method may involve managing state with a recursive helper function.

State Tracking for Averages

Track the sum and count of nodes for each level during traversal. You can store these in an array or hash map, where the key is the level and the value is an array with two elements: sum and count. After traversal, divide the sum by the count to compute the average for each level.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Both BFS and DFS solutions have a time complexity of O(n), where n is the number of nodes in the tree. The space complexity depends on the approach used: BFS requires O(w) space, where w is the width of the tree, and DFS requires O(h) space, where h is the height of the tree, for the call stack.

What Interviewers Usually Probe

Can the candidate explain why BFS or DFS is chosen for this problem?
Does the candidate account for variations in the tree structure, such as depth and width?
Can the candidate efficiently track state without excessive memory use?

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle cases with missing child nodes (null) during traversal.
Incorrectly calculating the average by not properly tracking node count or sum.
Misunderstanding tree structure, leading to wrong assumptions about level depth or node placement.

Follow-up variants

Modify the problem to return the sum instead of the average for each level.
Adapt the problem to handle non-binary trees or other tree variations.
Consider cases where all node values are the same, and optimize the algorithm accordingly.

FAQ

What is the main approach to solve the Average of Levels in Binary Tree problem?

The main approach is to perform a level order traversal (BFS) or depth-first traversal (DFS), tracking the sum and count of nodes at each level to calculate the average.

How do BFS and DFS differ in solving this problem?

BFS is more natural for this problem as it processes nodes level by level, while DFS can also be used by recursively managing node state at each level.

What is the time complexity of the solution?

The time complexity is O(n), where n is the number of nodes in the binary tree, as every node must be visited.

How does state tracking help in solving this problem?

State tracking is essential to track the sum and count of nodes at each level. This allows the calculation of averages once all levels are processed.

Can this problem be optimized for trees with extreme depth or width?

Yes, optimizing the tree traversal for large trees involves balancing space and time complexity, such as using DFS for smaller trees or BFS for more balanced trees.

terminal

Solution

Solution 1: BFS

We can use the Breadth-First Search (BFS) method to traverse the nodes of each level and calculate the average value of each level.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        q = deque([root])
        ans = []
        while q:
            s, n = 0, len(q)
            for _ in range(n):
                root = q.popleft()
                s += root.val
                if root.left:
                    q.append(root.left)
                if root.right:
                    q.append(root.right)
            ans.append(s / n)
        return ans

Solution 2: DFS

We can also use the Depth-First Search (DFS) method to calculate the average value of each level.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        q = deque([root])
        ans = []
        while q:
            s, n = 0, len(q)
            for _ in range(n):
                root = q.popleft()
                s += root.val
                if root.left:
                    q.append(root.left)
                if root.right:
                    q.append(root.right)
            ans.append(s / n)
        return ans

Continue Practicing

#623 add one row to tree #653 two sum iv input is a bst #655 print binary tree