Big O Practice: Level Order Traversal

from collections import deque

def level_order(root):
    if not root:
        return []
    res = []
    q = deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        res.append(level)
    return res

Variables

• n - number of nodes in the tree

Explanation

Each node is enqueued and dequeued once - **O(n)** time. The queue can hold up to `n/2` nodes (the widest level) so space is **O(n)**, not O(h).

More Big O practice problems · Today's daily problem