Binary Tree Level Order Traversal

Problem Summary

• Given a tree, return a list of nodes in the level order

Main Concepts Used

• Level-order Traversal
• Trees
• Tree Traversal
• Breadth First

Time & Space Complexity

• Time: $O(n)$ → Reason: Iterating through each node
• Space: $O(n)$ → Reason: Storing each node in a queue

Code

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        result = []
        q = deque([root])

        while q:
            current_level = []
            for _ in range(len(q)):
                head = q.popleft()
                current_level.append(head.val)
                if head.left:
                    q.append(head.left)
                if head.right:
                    q.append(head.right)
            result.append(current_level)
        return result