Forgetting null/base-case handling
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.
Build confidence with an intuition-first walkthrough focused on tree fundamentals.
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 - 1Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Tree
[3,9,20,null,null,15,7]
[3,9,20,15,7]
binary-tree-level-order-traversal)binary-tree-level-order-traversal-ii)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #637: Average of Levels in Binary Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> ans = new ArrayList<>();
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
int n = q.size();
long s = 0;
for (int i = 0; i < n; ++i) {
root = q.pollFirst();
s += root.val;
if (root.left != null) {
q.offer(root.left);
}
if (root.right != null) {
q.offer(root.right);
}
}
ans.add(s * 1.0 / n);
}
return ans;
}
}
// Accepted solution for LeetCode #637: Average of Levels in Binary Tree
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func averageOfLevels(root *TreeNode) []float64 {
q := []*TreeNode{root}
ans := []float64{}
for len(q) > 0 {
n := len(q)
s := 0
for i := 0; i < n; i++ {
root = q[0]
q = q[1:]
s += root.Val
if root.Left != nil {
q = append(q, root.Left)
}
if root.Right != nil {
q = append(q, root.Right)
}
}
ans = append(ans, float64(s)/float64(n))
}
return ans
}
# Accepted solution for LeetCode #637: Average of Levels in Binary Tree
# 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
// Accepted solution for LeetCode #637: Average of Levels in Binary Tree
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
pub fn average_of_levels(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<f64> {
let mut ans = vec![];
let mut q = VecDeque::new();
if let Some(root_node) = root {
q.push_back(root_node);
}
while !q.is_empty() {
let n = q.len();
let mut s: i64 = 0;
for _ in 0..n {
if let Some(node) = q.pop_front() {
let node_borrow = node.borrow();
s += node_borrow.val as i64;
if let Some(left) = node_borrow.left.clone() {
q.push_back(left);
}
if let Some(right) = node_borrow.right.clone() {
q.push_back(right);
}
}
}
ans.push((s as f64) / (n as f64));
}
ans
}
}
// Accepted solution for LeetCode #637: Average of Levels in Binary Tree
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #637: Average of Levels in Binary Tree
// /**
// * Definition for a binary tree node.
// * public class TreeNode {
// * int val;
// * TreeNode left;
// * TreeNode right;
// * TreeNode() {}
// * TreeNode(int val) { this.val = val; }
// * TreeNode(int val, TreeNode left, TreeNode right) {
// * this.val = val;
// * this.left = left;
// * this.right = right;
// * }
// * }
// */
// class Solution {
// public List<Double> averageOfLevels(TreeNode root) {
// List<Double> ans = new ArrayList<>();
// Deque<TreeNode> q = new ArrayDeque<>();
// q.offer(root);
// while (!q.isEmpty()) {
// int n = q.size();
// long s = 0;
// for (int i = 0; i < n; ++i) {
// root = q.pollFirst();
// s += root.val;
// if (root.left != null) {
// q.offer(root.left);
// }
// if (root.right != null) {
// q.offer(root.right);
// }
// }
// ans.add(s * 1.0 / n);
// }
// return ans;
// }
// }
Use this to step through a reusable interview workflow for this problem.
BFS with a queue visits every node exactly once — O(n) time. The queue may hold an entire level of the tree, which for a complete binary tree is up to n/2 nodes = O(n) space. This is optimal in time but costly in space for wide trees.
Every node is visited exactly once, giving O(n) time. Space depends on tree shape: O(h) for recursive DFS (stack depth = height h), or O(w) for BFS (queue width = widest level). For balanced trees h = log n; for skewed trees h = n.
Review these before coding to avoid predictable interview regressions.
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.