Long ago my students wanted binary tree problems, so I did a lot. I don’t think this one made the cut. This is from the archives, and according to my notes it took me a while to figure out the right iteration “pattern”. I think this stateful kind of iteration (the state is to help track the zigzag) is useful, though obviously here it’s contrived, so I think this is a good practice problem.

Approach

The key observation, and maybe this is too obvious, is that we can do BFS and keep track of the parity of what layer we’re in. If we’re in a left-to-right layer, we append our next children (who comprise the following layer) right-to-left, and vice-versa.

Realizing this in code, at least for me, was nontrivial. Here it is!

class Solution(object):
    def zigzagLevelOrder(self, root):
        if root is None:
            return []
        res = []
        currLevel = [root]
        reverse = False
        while currLevel:
            layer = []
            nextLevel = []
            # Drain the current level
            while currLevel:
                n = currLevel.pop()
                layer.append(n.val)
                if not reverse:
                    if n.left is not None:
                        nextLevel.append(n.left)
                    if n.right is not None:
                        nextLevel.append(n.right)
                else:
                    if n.right is not None:
                        nextLevel.append(n.right)
                    if n.left is not None:
                        nextLevel.append(n.left)
            res.append(layer[:])
            layer = []
            currLevel = nextLevel
            reverse = not reverse
        return res

Observations

Some thoughts:

1. As we’re updating our state, this has some nice exercises with variable lifetime stuff. You can see I append a copy of layer, rather than a reference to it. I am not 100% clear on how references and scoping work in Python, so I went conservative. Turning that around, this exercise helped “poke at” my understanding of references and scoping.
2. There’s something interesting going on about how the zig-zag-edness comes about implicitly from the tree structure and our iteration order.

Anyways. A weird tree question! More tree questions here.