Binary Tree Zigzag Level Order Traversal

Medium- Hard, https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/solution/

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:

1. Its good to point out the differences in the space complexity of the BFS (using a queue) and DFS (recursion ) approaches.
2. Both solutions are below.

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,

1. It is quite evident that we are traversing one level at a time, so we are doing a breadth first search. Therefore we will use a similar strategy to queue or using a recursive approach.
2. If using a queue, or BFS approach, Notice that since its zigzag traversal, every other level is traversed left to right, and vice versa. We can use a mechanism ( e.g. level % 2 == 0) , to chose a. how to pop nodes from the queue, b. how and where to add children ( front or back) in order to follow the zigzag pattern

Code BFS using a queue to traverse the tree.

1. Iterative approach using a queue to traverse the tree level by level and using an array to add nodes of a level.
2. A lot of visualization in the head is needed

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

• Time Complexity: O(N), where NN is the number of nodes in the tree.
• We visit each node once and only once.
• In addition, the insertion operation on either end of the deque takes a constant time, rather than using the array/list data structure where the inserting at the head could take the O(K) time where KKis the length of the list.
• Space Complexity: O(N) where NN is the number of nodes in the tree.
• The main memory consumption of the algorithm is the node_queue that we use for the loop, apart from the array that we use to keep the final output.
• As one can see, at any given moment, the node_queue would hold the nodes that are at most across two levels. Therefore, at most, the size of the queue would be no more than 2⋅L, assuming LL is the maximum number of nodes that might reside on the same level. Since we have a binary tree, the level that contains the most nodes could occur to consist all the leave nodes in a full binary tree, which is roughly L=N/2​. As a result, we have the space complexity of 2 * N/2=N in the worst case.

DFS apprach, the Recursive solution is slightly faster:

1. We add a deque() for each level_list inside final result array. Why? we need a O(1) operation for appending elements to the front of the list which only deque() has. appendleft()
2. We appendleft() for all the odd number levels ( 1,3,5 etc.).

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

• Time Complexity: O(N), where N is the number of nodes in the tree.
• Same as the previous BFS approach, we visit each node once and only once.
• Space Complexity: O(H), where H is the height of the tree, i.e. the number of levels in the tree, which would be roughly log⁡2N.
• Unlike the BFS approach, in the DFS approach, we do not need to maintain the node_queue data structure for the traversal.
• However, the function recursion would incur additional memory consumption on the function call stack. As we can see, the size of the call stack for any invocation of DFS(node, level) would be exactly the number of level that the current node resides on. Therefore, the space complexity of our DFS algorithm isO(log2​N) which is much better than the BFS approach.

Next Problems to try:

1. Sum of Left Leaves
2. Jump Game IV
3. Find Nearest Right Node in Binary Tree