from collections import defaultdict, deque

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        visited = set()
        levels = {}
        q = deque()
        q.append(root)
        visited.add(root)
        while len(q):
            cur = q.popleft()
            for child in [cur.left, cur.right]:
                if child and child not in visited:
                    visited.add(child)
                    levels[child] = levels[cur] + 1
                    q.append(child)
        lvl = defaultdict(list)
        for x, v in levels:
            lvl[v].append(x)

        return [lvl[i] for i in range(len(lvl))]