Binary Tree Zigzag Level Order Traversal

FILE TAGS: Medium

---

Intuition

• I chose to keep the same order of appending elements as Binary Tree Level Order Traversal, but simply stored the elements of the node backwards or forwards depending on if in an even or odd level.

Complexity

Runtime

$O(N)$ to traverse through each node (no extra runtime added for zigzagging since we are using a deque).

Space

$O(N)$ due to resultant array storing each element.

Code

# 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]]:
        if not root:
            return None
 
        res = []
        q = deque([root])
        count = 0
        while q:
            res.append(deque())
            node = None
            for _ in range(len(q)):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
 
                if count % 2 == 0:
                    res[count].append(node.val)
                else:
                    res[count].appendleft(node.val)
                    
            count += 1
        
        return res

Notes

Cards

START Basic Front: Binary Tree Zigzag Level Order Traversal Back: Store forwards or backwards to the result array depending on level, but keep same format as Binary Tree Level Order Traversal.

END

---

References

• Binary Tree Zigzag Level Order Traversal