# Teaching Kids Programming – Binary Tree Zigzag Level Order Traversal (via Breadth First Search Algorithm)

Teaching Kids Programming – Binary Tree Zigzag Level Order Traversal (via Breadth First Search Algorithm) | ninjasquad

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

```   3
/ \
9   20
/  \
15   7```

Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

Example 2:
Input: root = [1]
Output: [[1]]

Example 3:
Input: root = []
Output: []

Constraints:
The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100

### Binary Tree Zigzag Level Order Traversal (via Breadth First Search Algorithm)

The standard Breadth First Search (BFS) traverses level by level order, and each level from left to right. Here is the standard BFS in Python:

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ``` ```# 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: Optional[TreeNode]) -> List[List[int]]:         ans = []         if not root:             return ans         q = deque([root])         while q:             n = len(q)             cur = []             for _ in range(n):                 x = q.popleft()                 cur.append(x.val)                 for kid in (x.left, x.right):                     if kid:                         q.append(kid)                 ans.append(cur)         return ans```
```# 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: Optional[TreeNode]) -> List[List[int]]:
ans = []
if not root:
return ans
q = deque([root])
while q:
n = len(q)
cur = []
for _ in range(n):
x = q.popleft()
cur.append(x.val)
for kid in (x.left, x.right):
if kid:
q.append(kid)
ans.append(cur)
return ans```

The time/space complexity is O(N) where N is the number of the nodes given in the binary tree. And for the Zig-Zag, we just need to reverse the rows of the even numbers. Thus, with a slight modification, here is the Zig-zag traversal that reverses the even rows e.g. from right to left.

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ``` ```# 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: Optional[TreeNode]) -> List[List[int]]:         ans = []         if not root:             return ans         q = deque([root])         while q:             n = len(q)             cur = []             for _ in range(n):                 x = q.popleft()                 cur.append(x.val)                 for kid in (x.left, x.right):                     if kid:                         q.append(kid)             if len(ans) & 1:  # <----- if the next row is even number, we reverse it                 ans.append(cur[::-1])             else:                 ans.append(cur)         return ans```
```# 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: Optional[TreeNode]) -> List[List[int]]:
ans = []
if not root:
return ans
q = deque([root])
while q:
n = len(q)
cur = []
for _ in range(n):
x = q.popleft()
cur.append(x.val)
for kid in (x.left, x.right):
if kid:
q.append(kid)
if len(ans) & 1:  # <----- if the next row is even number, we reverse it
ans.append(cur[::-1])
else:
ans.append(cur)
return ans```

The extra time complexity here (ZigZag Traversal Order) is to reverse, which at most N//2 nodes. So thus, the time/space complexity is still O(N).

Of course, we can use Depth First Search Algorithm (both Recursive or Iterative) to perform a Zig-zag traversal order.

GD Star Rating