DSA sheet · Trees · BFS (level order) pattern

Zigzag Level Order Traversal

This is the problem right after plain level order traversal, and it builds directly on it. We still print the tree level by level, but the direction flips on every level: left to right, then right to left, then left to right again. The teacher first shows an easy brute force (do normal level order, then reverse every second level), then removes the extra reversing work with a deque (a list you can add to at both ends), and finally shows that the same answer is possible with DFS too. The real lesson: you can get a reversed list for free if you choose where to insert.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: level order, then reverse the odd levels
• Part B · Optimal BFS: insert at the front or the back of a deque
• Part C · Zigzag with DFS (carry the level number)
• Part D · Revision page

Part 0 · Before starting

The tree node

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val       # the number in this node
        self.left = left     # left child, or None
        self.right = right   # right child, or None

What is a "level"?

A level is a row of the tree. The root alone is level 0. Its children are on level 1. Their children are on level 2, and so on. A simple rule: a child's level = its parent's level + 1. We count from 0, the same way list indexes start at 0.

        3          ← level 0
       / \
      9   20       ← level 1
         /  \
        15   7     ← level 2

Plain level order traversal (the prerequisite)

The teacher says this video only makes sense if you already know level order traversal from the previous video. Here it is again, because Parts A and B are small edits of this exact code.

from collections import deque

class Solution:
    def levelOrder(self, root):
        ans = []
        if root is None:
            return ans
        queue = deque([root])
        while queue:
            size = len(queue)          # how many nodes are on THIS level
            level = []
            for i in range(size):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            ans.append(level)          # one finished row
        return ans

For the tree above it gives [[3], [9, 20], [15, 7]]. The key trick is size = len(queue): at the start of each round, the queue holds exactly one full level. So running the inner loop size times takes out that level and nothing more, even though we keep adding children at the back.

Part A · Brute force: level order, then reverse

LeetCode 103 · Binary Tree Zigzag Level Order Traversal

1The question in simple words

You get the root of a binary tree. Return the values level by level, as a list of lists, but in zigzag order:

• level 0: read left → right
• level 1: read right → left
• level 2: read left → right again, and keep alternating.

        3          → [3]
       / \
      9   20       ← [20, 9]
         /  \
        15   7     → [15, 7]

         1         → [1]
       /   \
      2     3      ← [3, 2]
     / \   / \
    4   5 6   7    → [4, 5, 6, 7]

Answer for example 1: [[3], [20, 9], [15, 7]]. Notice we return the values of the nodes, not the node objects.

2What the constraints tell us

• Number of nodes: 0 to 2000 → 0 is allowed, so the root can be None. In a BFS solution we must check this at the very start and return [], otherwise we would push None into the queue and crash on .val.
• The teacher's general rule about base cases:
  • BFS: the empty check is needed only when the tree can be empty. If the constraints promise at least one node, you can skip it, because the while queue loop stops by itself.
  • DFS: always write the base case, whatever the constraints say. Recursion has no loop condition; the base case is the only thing that stops it.
• Values: −100 to 100 → tiny numbers, a normal int is fine. We don't add or multiply them anyway.
• Why read constraints at all? They tell us (1) whether we need a base case, (2) whether int is big enough or we need long, and (3) whether a slow idea will pass. n ≤ 2000 is small, but we still aim for a clean O(n).

3Intuition: how to think about it

First decide BFS or DFS. The teacher's advice: whenever a question talks about levels, go with BFS first. BFS already walks the tree one level at a time, which is exactly what the output needs. DFS can also do it (Part C), but then we have to store and sort out levels ourselves.

Now picture the normal level order output and number the rows:

Even-index levels are already right. Odd-index levels are exactly backwards. So the simplest plan: do normal level order, then go over the result and reverse every row whose index is odd.

4Building the logic from the example

Step 1: get the plain level order

Run the Part 0 code unchanged. For example 1 we get [[3], [9, 20], [15, 7]].

Step 2: walk over the rows with their index

Row 0 → index is even → leave it. Row 1 → odd → reverse [9, 20] into [20, 9]. Row 2 → even → leave it. Done.

Why the teacher calls this "brute force"

• Filling the list of levels already costs O(n) time and O(n) space.
• Then we make a second pass and reverse rows. Reversing a row costs time equal to its length.
• She looks at the worst case: what is the biggest row we could ever reverse? In a full binary tree (every level completely filled) the last level holds about half of all nodes. With 7 nodes, the last level has 4. So one reversal can cost about n/2, which is still O(n).

         1          level 0: 1 node
       /   \
      2     3       level 1: 2 nodes
     / \   / \
    4   5 6   7     level 2: 4 nodes  ≈ n/2  (n = 7)

So the question becomes: can we avoid reversing altogether, and get the right order while we fill each row? That's Part B.

5Approach steps

1. If the root is None, return [].
2. Do normal level order traversal with a queue and the size trick, collecting each level as a list.
3. After the BFS is over, loop over the rows with their index.
4. If the index is odd, reverse that row in place.
5. Return the list of rows.

6Code (Python)

from collections import deque

class Solution:
    def zigzagLevelOrder(self, root):
        ans = []
        if root is None:                    # 0 nodes allowed
            return ans
        queue = deque([root])
        while queue:
            size = len(queue)
            level = []
            for i in range(size):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            ans.append(level)
        # second pass: flip every odd row
        for idx in range(len(ans)):
            if idx % 2 == 1:
                ans[idx].reverse()
        return ans

7Code line by line

8Dry run on example 1

9Complexity & remember

• Time O(n) for BFS + up to O(n) more for all the reversing (see the doubt above): linear, but two passes.
• Space O(n): the queue can hold a whole level (up to about n/2 nodes), and the answer holds all n values.

Part B · Optimal BFS with a deque

1The question, and 2 the constraints

Exactly the same as Part A: zigzag rows, 0 to 2000 nodes (so we keep the empty-tree check), small values. Only the way we build each row changes.

3Intuition: insert at the front to reverse for free

Say three values arrive in the order 1, 2, 3. Watch what happens with two ways of inserting:

Inserting every new value at the front gives the list already reversed. We never call reverse; the order comes out right while we insert.

But a normal Python list is slow at inserting at the front (insert(0, x) shifts every item, O(k)). We need a structure where adding at both ends is O(1). That's a deque ("double-ended queue"). In Python, collections.deque has append (back) and appendleft (front), both O(1). The teacher mentions that in Java a LinkedList does the same job (addLast / addFirst), and in C++ and Python you use a deque.

4Building the logic

Each row becomes a deque instead of a list

The outer answer can stay a normal list. Only the inner row needs to be a deque, because that's where we insert at the front or the back.

How do we know which end to use? A flag

Keep a boolean left_to_right:

• True → this row reads left to right → level.append(node.val) (back).
• False → this row reads right to left → level.appendleft(node.val) (front).

After a whole row is done (after the inner for loop), flip it: left_to_right = not left_to_right. If it was True it becomes False, and the other way round.

The two new pieces are the if/else around the insert and the flip after each row. Remove them and you're back to plain level order.

5Approach steps

1. If the root is None, return [].
2. Put the root in the queue. Set left_to_right = True.
3. While the queue isn't empty: size = len(queue), and make an empty deque level.
4. Pop size nodes. For each one: if left_to_right, append its value at the back, else at the front. Push its children (left, then right).
5. After the row: store list(level) in the answer and flip the flag.
6. Return the answer.

6Code (Python)

from collections import deque

class Solution:
    def zigzagLevelOrder(self, root):
        ans = []
        if root is None:
            return ans
        queue = deque([root])
        left_to_right = True
        while queue:
            size = len(queue)
            level = deque()                     # the row is a deque now
            for i in range(size):
                node = queue.popleft()
                if left_to_right:
                    level.append(node.val)      # back: normal order
                else:
                    level.appendleft(node.val)  # front: reversed for free
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            ans.append(list(level))
            left_to_right = not left_to_right   # flip for the next row
        return ans

7Code line by line

8Dry run on example 1

Yellow boxes = the level being popped. The second line shows the row deque as it grows.

On the fuller tree, level 2 would be popped as 4, 5, 6, 7 with the flag True → row [4, 5, 6, 7]. If there were a level 3, its values would go in with appendleft and come out reversed.

9Complexity & remember

• Time O(n): every node is pushed once and popped once. append and appendleft on a deque are O(1), and so is pushing a child. One pass, no reversing.
• Space O(n): the queue holds at most one full level, which in a full tree is about n/2 nodes, still O(n).
• On LeetCode this ran faster than the brute force, because nothing is reversed after the BFS.

Part C · Zigzag with DFS

1The question

Same output. The teacher adds this part because an interviewer may ask: "Can you also do it with DFS?" Her answer: yes, it's possible, but since the question itself is about levels, BFS is the better choice. As a beginner, you should still know both.

For this part she uses a slightly different tree, with an extra node 8 under 9, so that DFS has to come back to an old level later:

         3          level 0 → [3]
       /   \
      9     20      level 1 ← [20, 9]
     /     /  \
    8     15   7    level 2 → [8, 15, 7]

2What the constraints tell us

• 0 nodes allowed, and this is recursion → the base case if root is None: return is a must. It also handles the empty tree: nothing gets added, and we return [].
• n ≤ 2000 → the recursion depth is at most 2000 in the worst case (a straight-line tree). That's deeper than Python's default recursion limit (1000), so a truly skewed 2000-node tree could hit RecursionError. One more reason BFS is preferred here.

3Intuition: give every call a level number

DFS does not go level by level. From 3 it dives to 9, then to 8, then comes back up and goes to 20. So how does it know that 9 and 20 belong in the same row?

The teacher's idea: pass the level number into every call. The root gets level 0. When a node calls its children, it passes its own level + 1. Each call on the call stack remembers its own level, so when we come back to 3 after finishing 9's side, 3 still knows it's level 0, and it gives 20 level 1.

Then we use that level as the index of the row in the answer: a node on level 2 goes into ans[2].

4Building the logic

Plain DFS with a level (what she draws first)

She first traces only the levels: 3 (level 0) → 9 (1) → 8 (2) → 8's children are None → return → 9's right is None → return → back to 3 → 20 (0 + 1 = 1) → 15 (2) → 7 (2). The levels come out correctly, but nothing is stored yet. So we add storing.

When do we need a new row? level == len(ans)

At the start, ans is empty. We don't know how many levels the tree has, so we create rows as we discover them:

• At 3: level 0, len(ans) is 0 → they're equal → this is the first time we reach level 0 → add a new empty row.
• At 9: level 1, len(ans) is 1 → equal → first time on level 1 → add a row.
• At 8: level 2, length 2 → add a row.
• At 20: level 1, but len(ans) is now 3 → not equal → row 1 already exists, so don't create one; just use it.

Get a handle on the row

After making sure the row exists, take it out once: cur = ans[level]. In Java the teacher has to type-cast it to a LinkedList; in Python, cur simply points to the same deque, so adding to cur adds to ans[level].

Back or front? Use the level itself

• level % 2 == 0 (even) → cur.append(val)
• odd → cur.appendleft(val)

Again each row is a deque, for the same reason as Part B: no reversing later.

5Approach steps

1. Make an empty ans, call dfs(root, 0), then return the rows as lists.
2. In dfs(node, level): if node is None, return.
3. If level == len(ans), append a new empty deque.
4. cur = ans[level]. Even level → append at the back; odd → append at the front.
5. Call dfs(node.left, level + 1), then dfs(node.right, level + 1).

6Code (Python)

from collections import deque

class Solution:
    def zigzagLevelOrder(self, root):
        ans = []
        self.dfs(root, 0, ans)
        return [list(row) for row in ans]

    def dfs(self, root, level, ans):
        if root is None:                    # base case: stops the recursion
            return
        if level == len(ans):               # first visit to this level
            ans.append(deque())
        cur = ans[level]
        if level % 2 == 0:
            cur.append(root.val)            # even level: back
        else:
            cur.appendleft(root.val)        # odd level: front
        self.dfs(root.left, level + 1, ans)
        self.dfs(root.right, level + 1, ans)

7Code line by line

8Dry run on the tree with 8

1. dfs(3, 0): len(ans) = 0 = level → new row. Even → ans = [[3]].
2. dfs(9, 1): len 1 = level → new row. Odd → front → ans = [[3], [9]].
3. dfs(8, 2): len 2 = level → new row. Even → ans = [[3], [9], [8]].
4. dfs(None, 3) twice (8's children) → return. 8 is done and leaves the stack. 9's right is None → return. 9 leaves the stack.
5. Back in dfs(3, 0), which still remembers level 0 → dfs(20, 1): len is 3, not 1 → no new row. Odd → front → row 1 = [20, 9].
6. dfs(15, 2): row exists. Even → back → row 2 = [8, 15]. Its children are None → return.
7. dfs(7, 2): even → back → row 2 = [8, 15, 7]. Children None → return. 20 returns, then 3 returns. The stack is empty.
8. Final: [[3], [20, 9], [8, 15, 7]] ✓

Each box remembers its own level. That's how 20 knows to use 0 + 1 = 1 even though 9's whole side ran in between.

9Complexity & remember

• Time O(n): each node is visited once; each insert is O(1).
• Space O(n) worst case. The call stack only holds the current path: in our tree the most it ever held was 3 calls, which is the number of levels. But if the tree is a straight chain, every node waits on the stack, so the worst case is O(n). (Plus the answer itself, which holds n values.)
• BFS and DFS have the same complexity here. The teacher still prefers BFS for any level-order question, because it matches the question directly.

Part D · Revision page

t1 = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
t2 = TreeNode(3, TreeNode(9, TreeNode(8)), TreeNode(20, TreeNode(15), TreeNode(7)))
full = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7)))

s = Solution()
print(s.zigzagLevelOrder(t1))     # [[3], [20, 9], [15, 7]]
print(s.zigzagLevelOrder(t2))     # [[3], [20, 9], [8, 15, 7]]
print(s.zigzagLevelOrder(full))   # [[1], [3, 2], [4, 5, 6, 7]]
print(s.zigzagLevelOrder(None))   # []

Based on this video: Binary Tree Zigzag Level Order Traversal | BFS & DFS