# Binary Tree Zigzag Level Order Traversal

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:

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,

Code BFS using a queue to traverse the tree.

`# 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`

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

DFS apprach, the Recursive solution is slightly faster:

`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

Next Problems to try:

## More from Technical Interviews Preparation

Currently preparing for interviews