print levels of binary tree in zig zag (alternating) order

For a binary tree, print 1st level left-right, 2nd level r-l, 3rd level l-r and so on. For bfs with all nodes l-r, use a queue.

Use two stacks. stack1 has nodes from odd levels 1, 3, etc. and stack2 has nodes from even levels 2, 4, etc. If the 2nd level is to be printed r-l, then you push left child first and then right child into stack2 (right-most child on top-of-stack so it's printed first). Reverse the children order for stack1 (left-most child on top-of-stack so it's printed first).

//1st level l-r, 2nd level r-l, 3rd level l-r ...
void bfs_alternating(Node root):
    stack1 = new stack()
    stack2 = new stack()
    stack1.push(root)
    while (!stack1.isEmpty()):
        while (!stack1.isEmpty()):
            Node node = stack1.pop()
            print(node.value)
            // null checks omitted for brevity
            stack2.push(node.left)
            stack2.push(node.right)
        while (!stack2.isEmpty()):
            Node node = stack2.pop()
            print(node.value)
            // null checks omitted for brevity
            stack1.push(node.right)
            stack1.push(node.left)

Or using queue. Needs more space (2 levels).

//1st level l-r, 2nd level r-l, 3rd level l-r ...
bfs_alternating(root):
    q = new
    depth = 1
    q.enqueue({node: root, depth: depth})
    nodes = new
    while !q.isempty():
        while !q.isempty() && q.peek().depth == depth:
            node = q.dequeue().node
            nodes.add(node)
            // null checks omitted for brevity
            q.enqueue({node: node.left, depth: depth +1})
            q.enqueue({node: node.right, depth: depth +1})
        // reverse even depths
        if depth & 1 != 0: // depth % 2 != 0
            nodes.reverse()
        foreach n in nodes:
            print(n)
        print(newline)
        nodes.clear()
        depth++

[Hat tip to AN]