Just traverse using BFS and if level is even then store in normal order else store level elements in reversed order

```
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
# First find out height
height = self.height(root)
result = []
# Here the approch is BFS
# Hence to simulate these conditions we will use simple for loop
for i in range(height):
output = self.printLevelOrder(root,i, [])
if i % 2 == 0:
result.append(output)
else:
result.append(list(reversed(output)))
return result
# This function basically reaches to the level first then appends result to it
def printLevelOrder(self, node, height, result):
if node == None:
return
# If reached to level add val
if(height == 0):
result.append(node.val)
# Else go left and right with one less level
# Here what you are doing is that decreasing height by 1 until you get height 0 which is nothing but desired level
# So lets say we want to reach level 2 then we will pass height as 2 then decrease it till becomes zero and simultanously go deep into tree at every recursive call
if height > 0:
self.printLevelOrder(node.left, height-1, result)
self.printLevelOrder(node.right, height-1, result)
return result
# Find out height
def height(self, root):
if root == None:
return 0
return 1+ max(self.height(root.left),self.height(root.right))
```