# Binary Tree Zigzag Level Order Traversal

Medium- Hard, https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/solution/

Given a binary tree, return the *zigzag level order* traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

**During interview:**

- Its good to point out the differences in the space complexity of the BFS (using a queue) and DFS (recursion ) approaches.
- Both solutions are below.

For example:

Given binary tree `[3,9,20,null,null,15,7]`

,

` 3`

/ \

9 20

/ \

15 7

return its zigzag level order traversal as:

`[`

[3],

[20,9],

[15,7]

]

**Intuition,**

- It is quite evident that we are traversing one level at a time, so we are doing a breadth first search. Therefore we will use a similar strategy to queue or using a recursive approach.
- 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

**Code BFS using a queue to traverse the tree.**

- Iterative approach using a queue to traverse the tree level by level and using an array to add nodes of a level.
- 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 = right

class 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

Runtime: 36 ms, faster than 31.74% of Python3 online submissions for Binary Tree Zigzag Level Order Traversal.

Memory Usage: 14.5 MB, less than 32.79% of Python3 online submissions for Binary Tree Zigzag Level Order Traversal.

**Complexity Analysis**

- Time Complexity: O(N), where N
*N*is the number of nodes in the tree. - 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 K
*K*is the length of the list. - Space Complexity: O(N) where N
*N*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 L*L*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.

**DFS apprach, the Recursive solution is slightly faster:**

- We add a deque() for each level_list inside final result array. Why? we need a O(1) operation for appending elements to the
**front of the list**which only**deque() has. appendleft()** - 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

Runtime: 28 ms, faster than 88.73% of Python3 online submissions for Binary Tree Zigzag Level Order Traversal.

Memory Usage: 14.6 MB, less than 9.28% of Python3 online submissions for Binary Tree Zigzag Level Order Traversal.

**Complexity Analysis**

- Time Complexity: O(N), where N is the number of nodes in the tree.
- 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 log2N. - 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**. As we can see, the size of the call stack for any invocation of*function call stack*`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.

Next Problems to try: