deepSWE.io

Binary Tree Zigzag Level Order Traversal

TreesBFS

25 min

Problem Statement

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).

Example

Example 1:

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

Output: [[3],[20,9],[15,7]]

Solution: Breadth-First Search (BFS)

The problem can be solved efficiently using a Breadth-First Search. We traverse the tree level by level, and for each level, we decide whether to add the nodes from left to right or right to left.

Algorithm Steps

Create a queue and add the root node.
Keep track of the current level number.
While the queue is not empty, get the number of nodes at the current level.
If the level is even, add the nodes to the level list from left to right.
If the level is odd, add the nodes to the level list from right to left.
Enqueue the children of the nodes at the current level.

Final Result:

[

]

Start of level. Level size: 1. Direction: left to right.

Binary Tree Zigzag Level Order Traversal Solution


# 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
from collections import deque

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
            
        res = []
        q = deque([root])
        left_to_right = True
        
        while q:
            level_size = len(q)
            level = deque()
            
            for _ in range(level_size):
                node = q.popleft()
                
                if left_to_right:
                    level.append(node.val)
                else:
                    level.appendleft(node.val)
                
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            
            res.append(list(level))
            left_to_right = not left_to_right
            
        return res