Framework Thinking - Neetcode 150 - Binary Tree Level Order Traversal

Here is solutions for Binary Tree Level Order Traversal.

1. Understand the problem

We are given the root of a binary tree. Our task is to return the level order traversal of its nodes’ values.

Level order traversal means:

  • Visit all nodes level by level

  • From left to right within each level

      3
     / \
    9  20
       / \
      15  7

Output: [[3], [9,20], [15,7]]

2. Clarify constraints, asks 4 - 5 questions including edge cases.

  1. Can the tree be empty (root = None)?

=> Yes → return [].

  1. Can there be duplicate values?

=> Yes, values don’t affect structure.

  1. Is this always a binary tree (max 2 children)?

=> Yes.

  1. How large can the tree be?

=> Up to ~10^4 or more nodes → O(n) solution required.

  1. Do we need stable left-to-right order?

=> Yes, strictly left before right.

3. Explore examples.

  1. Example 1
Input: root = [1,2,3]
Tree:
    1
   / \
  2   3

Output: [[1], [2,3]]
  1. Example 2
Input: root = []
Output: []
  1. Example 3
    1
     \
      2
       \
        3

Output: [[1], [2], [3]]

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. BFS - Time O(N), Space O(N / 2)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []

        q = collections.deque()
        q.append(root)

        while q:
            qLen = len(q)
            level = []
            for i in range(qLen):
                node = q.popleft()
                if node:
                    level.append(node.val)
                    q.append(node.left)
                    q.append(node.right)
            if level:
                res.append(level)

        return res

  • Time: O(N)

  • Space: O(N / 2)

4.2. DFS with level tracking - Time O(N), Space O(H), worst case O(N), best case O(logN)

  • You cannot reach depth = 3 before creating depth = 0,1,2.

So:

  • When you reach depth = k

  • res already has k lists

  • So len(res) is either k or k+1

  • Never smaller than k

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []

        def dfs(node, depth):
            if not node:
                return None
            if len(res) == depth:
                res.append([])

            res[depth].append(node.val)
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)

        dfs(root, 0)
        return res

  • Time: O(N).

  • Space: O(H).

5. Implement solutions.

6. Dry run testcases.

December 3, 2025