Binary Tree Level Order Traversal

LeetCode 102 · View on LeetCode

BFS using a deque. Process all nodes at the current level before moving to the next. Collect values level by level.

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order(root: TreeNode | None) -> list[list[int]]:
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

if __name__ == '__main__':
    tree = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
    print(level_order(tree))  # [[3], [9, 20], [15, 7]]

    print(level_order(TreeNode(1)))  # [[1]]
    print(level_order(None))          # []