Binary Tree Level Order Traversal

BFS
https://www.leetcode.com/problems/binary-tree-level-order-traversal

# Solution

Let nn be the number of TreeNodes.

# Iterative Layered BFS

Complexity

time: O(n)O(n)
space: O(n)O(n)

def levelOrder(self, root: TreeNode) -> List[List[int]]:
    queue = [root]
    res = []
    if not root: return res

    while queue:
        level = []
        for _ in range(len(queue)):
            curr = queue.pop(0)
            level.append(curr.val)
            if curr.left: queue.append(curr.left)
            if curr.right: queue.append(curr.right)
        res.append(level)

    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# Recursive Layered BFS

Complexity

time: O(n)O(n)
space: O(n)O(n)

def levelOrder(self, root: TreeNode) -> List[List[int]]:
    res = []
    if not root: return res

    def bfs(node, level):
        if len(res) == level:
            res.append([])
        res[level].append(node.val)
        if node.left:
            bfs(node.left, level+1)
        if node.right:
            bfs(node.right, level+1)

    bfs(root, 0)
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15