Binary Tree Zigzag Level Order Traversal

Problem Summary

• Given a Binary Tree, return the zigzag level order traversal

Approach Taken

• Do a level order traversal
• Store each level's nodes
• Add them in reverse every other time

Main Concepts Used

• Trees
• Tree Traversal
• Level-order Traversal
• Breadth First

Time & Space Complexity

• Time: $O(n)$ → Reason: Processing each node
• Space: $O(b)$ → Reason: Max breadth of the tree, If the tree has height h, the last level can have up to $2^{(h-1)}$ nodes.

Code

    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        result = []
        shouldBeReversed = False
        q = deque([root])

        while q:
            level = []
            for _ in range(len(q)):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            if shouldBeReversed:
                level.reverse()
            shouldBeReversed = not shouldBeReversed
            result.append(level)
        return result

Common Mistakes / Things I Got Stuck On

• Not setting the correct initial value of shouldBeReversed