# Binary Tree Zigzag Level Order Traversal

1. Both solutions are below.
`    3   / \  9  20    /  \   15   7`
`[  ,  [20,9],  [15,7]]`
1. If using a queue, or BFS approach, Notice that since its zigzag traversal, every other level is traversed left to right, and vice versa. We can use a mechanism ( e.g. level % 2 == 0) , to chose a. how to pop nodes from the queue, b. how and where to add children ( front or back) in order to follow the zigzag pattern
1. A lot of visualization in the head is needed
`# Definition for a binary tree node.# class TreeNode:#     def __init__(self, val=0, left=None, right=None):#         self.val = val#         self.left = left#         self.right = rightclass Solution:    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:                if not root:            return None                res = []                q = collections.deque()        q.append(root)        level = 0                while q:            nodes_level = []                        for _ in range(len(q)):                if level % 2 == 0:                    # first root is traversed from left to right                    # [node, node siblings from left to right ...]                    node = q.popleft()                else:                    # # [node siblings from left to right...,  node]                    node = q.pop()                                nodes_level.append(node.val)                                if level % 2 == 0:                    # root's children will be traversed right to left, so                     # we append left to the end of queue first and then append right.                    # Children will be inserted [parents' siblings..., left, right]                    if node.left:                        q.append(node.left)                    if node.right:                        q.append(node.right)                else:                    # Children will be inserted [left, right, ...parents' siblings]                    if node.right:                         q.insert(0, node.right)                    if node.left:                         q.insert(0, node.left)                                level += 1                    res.append(nodes_level)                    return res`
• We visit each node once and only once.
• In addition, the insertion operation on either end of the deque takes a constant time, rather than using the array/list data structure where the inserting at the head could take the O(K) time where KKis the length of the list.
• Space Complexity: O(N) where NN is the number of nodes in the tree.
• The main memory consumption of the algorithm is the `node_queue` that we use for the loop, apart from the array that we use to keep the final output.
• As one can see, at any given moment, the `node_queue` would hold the nodes that are at most across two levels. Therefore, at most, the size of the queue would be no more than 2⋅L, assuming LL is the maximum number of nodes that might reside on the same level. Since we have a binary tree, the level that contains the most nodes could occur to consist all the leave nodes in a full binary tree, which is roughly L=N/2​. As a result, we have the space complexity of 2 * N/2=N in the worst case.
1. We appendleft() for all the odd number levels ( 1,3,5 etc.).
`class Solution:    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:        if not root: return        res = []                def traverse(node, level):            if len(res) == level:                res.append(collections.deque())                            if level % 2 == 0:                    res[level].append(node.val)            else:                res[level].appendleft(node.val)                if node.left: traverse(node.left, level+1)             if node.right: traverse(node.right, level+1)                 traverse(root, 0)        return res`
• Same as the previous BFS approach, we visit each node once and only once.
• Space Complexity: O(H), where H is the height of the tree, i.e. the number of levels in the tree, which would be roughly log⁡2N.
• Unlike the BFS approach, in the DFS approach, we do not need to maintain the `node_queue` data structure for the traversal.
• However, the function recursion would incur additional memory consumption on the function call stack. As we can see, the size of the call stack for any invocation of `DFS(node, level)` would be exactly the number of `level` that the current node resides on. Therefore, the space complexity of our DFS algorithm isO(log2​N) which is much better than the BFS approach.

--

--