Teaching Kids Programming – Average Level of Binary Tree via Depth First Search Algorithm

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].

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

We know we can use Breadth First Search (BFS) Algorithm to compute the average level of a binary tree. We also can use the Depth First Search Algorithm to traverse the binary tree and record the nodes for each level – and then compute the average for each level and return as a list.

Compute the Average Levels of Binary Tree via Depth First Search Algorithm

We have a list to store the nodes for each level – and we perform the Depth First Search (DFS) algorithm and recursively pass on the level (which can be used to index the array). If the array length is less or equal to the level (index 0) – then we append a new subarray – otherwise we append the node to that particular level.

# 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 []        
        def dfs(root, lvl, res):
            if not root:
                return
            if lvl >= len(res):
                res.append([root.val])
            else:
                res[lvl].append(root.val)
            dfs(root.left, lvl + 1, res)
            dfs(root.right, lvl + 1, res)                
        res = []
        dfs(root, 0, res)
        return [sum(x)/len(x) for x in res]

And finally, we return the average for each levels using list comprehension.

–EOF (The Ultimate Computing & Technology Blog) —