Binary Tree Zigzag Level Order Traversal

The algorithm uses BFS with a trace of the level.

While the queue is not empty:

If the current level is different from the precedent that means that we pass through all of the precedent nodes and we can now store the list of precedent nodes (and reinitialize this list). If the level of the precedents nodes is odd we reverse the order before storing it.

If the current node is not None we add his value to the list and add its children to the queue

from collections import deque

def zigzagLevelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    q, level, level_list = deque(), 0, []
    q.append((root, level))

    out = []
    while q:
        node, i = q.popleft()
        # if we start a new level then we need to store the precedent level values
        if i != level:
            if i % 2 == 0:
                level_list = level_list[::-1]
            out.append(level_list)
            level, level_list = i, []
        
        # if the node is not Node, add its value to the list and add its children to the queue
        if node:
            level_list.append(node.val)
            q.extend(((node.left, i+1), (node.right, i+1)))

    return(out)