# Python using stack

• Here I used `total` to represent the sum of each level's node values, and `count` to represent the number of nodes in each level.

``````class Solution(object):
def averageOfLevels(self, root):
"""
:type root: TreeNode
:rtype: List[float]
"""
stack = [(root, 1)] if root else []
total = collections.defaultdict(int)
count = collections.defaultdict(int)
while stack:
node, level = stack.pop()
total[level] += node.val
count[level] += 1
if node.left:
stack.append((node.left, level+1))
if node.right:
stack.append((node.right, level+1))
return [1.0 * total[level] / count[level] for level in sorted(total.keys())]
``````

• I don't think defaultdict has a guarantee of being iterated in a certain order, so your last line looks flawed. (Edit: after adding the `sorted`, it's now ok)

• @StefanPochmann
Not sure about if it guarantee the sorted order either. Thus I made like 10 test cases and all of them shows it has a sorted order. Didn't find anything related after googling 10 minutes... Anyway, let me edit it before I found some evidence. :)

• I'm not sure about `defaultdict`, but for `dict` the order isn't defined:

CPython implementation detail: Keys and values are listed in an arbitrary order which is non-random, varies across Python implementations, and depends on the dictionary’s history of insertions and deletions.
-- https://docs.python.org/2/library/stdtypes.html#dict.items

I didn't find something like that for `defaultdict` in the documentation, but since it's a subclass of `dict`, it's probably equivalent.

With `int` keys in CPython you'll likely get away with it because of how it's implemented, but for example with strings it can fail:

``````>>> list({i: i for i in range(10)})
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> list({str(i): i for i in range(10)})
['1', '0', '3', '2', '5', '4', '7', '6', '9', '8']
``````

That's Python 2 and Python 3.5 behaves similarly. In Python 3.6 the implementation of `dict` was changed and now it happens to be the insertion order (at least if you only insert):

``````>>> list({str(i): i for i in range(10)})
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
>>> list({str(i): i for i in range(10)[::-1]})
['9', '8', '7', '6', '5', '4', '3', '2', '1', '0']
``````

But it's still an implementation detail.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.