Teaching Kids Programming – Breadth First Search Algorithm to Compute Average of Levels in Binary Tree


Teaching Kids Programming: Videos on Data Structures and Algorithms

Given the 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,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].

average-of-levels-in-binary-tree Teaching Kids Programming - Breadth First Search Algorithm to Compute Average of Levels in Binary Tree algorithms BFS python teaching kids programming youtube video

Example 2:
Input: root = [3,9,20,15,7]
Output: [3.00000,14.50000,11.00000]

Compute the Average of the Levels in Binary Tree using BFS Algorithm

As we are expanding the nodes of the next level in binary tree using Breadth First Search, we can compute the average then and push it to the result.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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: TreeNode) -> List[float]:
        if not root:
            return []
        q = deque([root])
        ans = []
        while q:
            n = len(q)
            s = 0
            for _ in range(n):
                cur = q.popleft()
                s += cur.val
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            ans.append(s/n)
        return ans
# 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: TreeNode) -> List[float]:
        if not root:
            return []
        q = deque([root])
        ans = []
        while q:
            n = len(q)
            s = 0
            for _ in range(n):
                cur = q.popleft()
                s += cur.val
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            ans.append(s/n)
        return ans

The time complexity is O(N) where N is the number of the nodes in binary tree and the space complexity is O(N) as we are using a queue to implement the Breadth First Search algorithm.

See also: How to Compute Average of Levels in Binary Tree?

We can use the Depth First Search Algorithm to compute the average levels of the binary tree: Teaching Kids Programming – Average Level of Binary Tree via Depth First Search Algorithm

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
490 words
Last Post: How to List the Boot Configuration Properties on Windows using VBScript?
Next Post: Javascript (NodeJS) Function to Get the Downvote Power of Account on Steem Blockchain

The Permanent URL is: Teaching Kids Programming – Breadth First Search Algorithm to Compute Average of Levels in Binary Tree

Leave a Reply