{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Binary Tree Level Order Traversal – Solution & Complexity

Interview solutions
/
Binary Tree Level Order Traversal

1. Recognize the Pattern

The key pattern is: BFS processes one queue level at a time. Identify the state and invariant before coding.

2. Build the Algorithm

Advance one state transition at a time. Mark or update state before exploring dependent work.

3. Check Edge Cases

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

4. Solution and Complexity

Time: O(n). Space: O(n).

def level_order(root: TreeNode) -> list[list[int]]:
    if root is None:
        return []
    answer, queue, head = [], [root], 0
    while head < len(queue):
        level = []
        for _ in range(len(queue) - head):
            node = queue[head]; head += 1
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        answer.append(level)
    return answer

FAQ

See also

Practice Binary Tree Level Order Traversal online (run code in the browser)Clone Graph solution (medium)Invert Binary Tree solution (easy)Lowest Common Ancestor of a BST solution (medium)Maximum Depth of Binary Tree solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?