Skip to main content

< Back to Data Structures and Algorithms

LeetCode 637 · Trees

Average of Levels in Binary Tree

The average value on each level of a binary tree, a level at a time, breadth first.

Step through it

Examples
Edge cases
root
9157203

Step 0 of 9

Output

Running… play or step to the end.

The code

/**
 * Definition for a binary tree node.
 * const TreeNode = (val, left, right) => {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * Traverses a binary tree level by level (Breadth first search).
 * Calculates the average value on each level of the tree.
 * @param {TreeNode} root // The starting ancestor node.
 * @return {number[]} // Each value is the average for that level
 */
 const averageOfLevels = root => {
  // Root doesn't exist, return an empty array.
  if (!root) return []
  
  // Will contain the average value for each level of the tree, as an entry in the array.
  const averageForEachLevel = []
  // Using a queue data structure in-order to traverse the tree level by level. Start with root.
  let queue = [root]
  
  /* As we traverse level by level, we will be appending / removing items from the queue.
     When the queue is empty, we have traversed all levels and should stop iterating. */
  while (queue.length) {
      // Will contain the sum of each value on the current level.
      let totalForLevel = 0
      
      queue.forEach(item => {
          totalForLevel += item.val
      })
      
      // Calculate and push the average value.
      if (queue.length) {
          const averageForThisLevel = totalForLevel / queue.length

          averageForEachLevel.push(averageForThisLevel)
      }
      
      // Capture the initial size of the array, before we manipulate it when queuing the next level.
      const size = queue.length
      
      // Iterate on each item in the queue.
      for (let i = 0; i < size; i++) {
          // Remove the current node from the queue
          let currentNode = queue.shift()
          
          // Push its children (left + right) onto the queue.
          if (currentNode.left) {
              queue.push(currentNode.left)
          }
          if (currentNode.right) {
             queue.push(currentNode.right)
          }
      }
  }
  
  // Return the array containing the average value of each level within the binary tree.
  return averageForEachLevel
}

View it on GitHub (opens in a new tab)