Return to Revisions

Building on @Graipher's answer, I don't think you need to explicitly maintain the state of the direction of iteration in the is_left variable. All you need to do is to alternate between iter and reversed to traverse your nodes for printing... and alternate indefinitely.

itertools.cycle is exactly meant for that.

You also don't need to pop (or popleft) items from wq since you use an intermediate list and you override wq with that intermediate list right after iterating over it. An explicit loop will perform better here:

import itertools
class Node:
 def __init__(self, value):
 self.value = value
 self.left = None
 self.right = None
def zigzag(root):
 nodes = [root]
 for pattern in itertools.cycle((iter, reversed)):
 # Print current layer
 if not nodes:
 return
 print [node.value for node in pattern(nodes)]
 
 # Collect children
 children = []
 for node in nodes:
 if node.left:
 children.append(node.left)
 if node.right:
 children.append(node.right)
 nodes = children