Binary Tree Zigzag Level Order Traversal

Problem

Qn - Binary Tree Zigzag Level Order Traversal

Approach

It seems pretty simple on first glance, just a BFS, and then some additional logic to alternate left and right to achieve the zigzag, but implementing it seems pretty difficult. We first have to take care of the order in which we insert into the frontier, then take care of the order that we read the children and the order we insert into the result array.

I thought of an easier way. I realised that we can just BFS the normal way, keep that the same, and keep the order in which we read the children the same. What change is the way we insert into the result array. We can create a double ended queue for each result element (each level), and when it is a left - right, we can just insert it as per normal, and when it is right - left, we can append left. The double ended queue allows us to do it in O(1) time. I guess you can see this as a hack for the obvious solution, which is to do the normal BFS then reverse each result element.

But when retuning, I realise that we cannot return as a deque element, and it needs to be an array. We will then have to convert the deque element to a list, which takes O(n) time, so it is essentially the same as the obvious solution. But both would still give us O(2n).

Finally when reading the solution, I realised that we could actually find out the number of nodes in each level, then pre-create the array, and then populate it from left to right or right to left, using the indexes. This will make it truly O(n), and it’s pretty smart, since we don’t need to go through the complicated switching mechanism

Complexity

• Time: O(n)
• Space: O(n)

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 []
        isLeftRight = True
        res = []
        queue = deque([root])
 
        while queue:
            # get level information
            nodes_in_level = len(queue)
            res_elem = [0] * nodes_in_level
 
            # populate the result element
            for i in range(nodes_in_level):
                node = queue.popleft()
                if isLeftRight: res_elem[i] = node.val
                else: res_elem[nodes_in_level - i - 1] = node.val
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
 
            res.append(res_elem)
            isLeftRight = not isLeftRight
 
        return res

The O(2n) approach

# 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]]:
        result = []
        isLeftRight = False
        frontier = deque([(root, 0)])
 
        while frontier:
            node, level = frontier.popleft()
            if not node: break
            if len(result) == level: 
                result.append(deque())
                isLeftRight = not isLeftRight
 
            if isLeftRight: result[level].append(node.val)
            else: result[level].appendleft(node.val)
            
            if node.left: frontier.append((node.left, level+1))
            if node.right: frontier.append((node.right, level+1))
 
        for i,r in enumerate(result): result[i] = list(r)
 
        return result