Let's visit every node of the tree once, keeping track of what depth we are on. We can do this with a simple DFS.
When we visit a node, info[depth] will be a two element list, keeping track of the sum of the nodes we have seen at this depth, and the number of nodes we have seen. This is necessary and sufficient to be able to compute the average value at this depth.
At the end of our traversal, we can simply read off the answer.
def averageOfLevels(self, root): info =  def dfs(node, depth = 0): if node: if len(info) <= depth: info.append([0, 0]) info[depth] += node.val info[depth] += 1 dfs(node.left, depth + 1) dfs(node.right, depth + 1) dfs(root) return [s/float(c) for s, c in info]