[Top Interview 150] 103. Binary Tree Zigzag Level Order Traversal

Solution)

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # Base Case
        if not root: return []
        
        # zig is a list that saves nodes from right to left
        # zag is a list that saves nodes from left to right
        # res is a final list that will have zigzagged nodes' vals
        zig, zag, res = [], [], []
        
        # Initialization
        zig.append(root)

        # Iterate the entire tree
        while zig or zag:
            # This temporary list will save the current level nodes' values
            curr_lvl = []

            # If we need to iterate from left to right
            if zig:
                for _ in range(len(zig)):
                    # Get vals from left to right
                    cur = zig.pop()
                    curr_lvl.append(cur.val)

                    # Save nodes from left to right
                    if cur.left: zag.append(cur.left)
                    if cur.right: zag.append(cur.right)
            
            # If we need to iterate from right to left
            else:
                for _ in range(len(zag)):
                    # Get vals from right to left
                    cur = zag.pop()
                    curr_lvl.append(cur.val)

                    # Save nodes from right to left
                    if cur.right: zig.append(cur.right)
                    if cur.left: zig.append(cur.left)

            # Append the current level nodes' values to res
            res.append(curr_lvl)
        
        return res

 
Problem: LeetCode
 
Time Complexity: O(n)
Space Complexity: O(n)
 

Explanation)

We'll have two arrays.
One will save nodes from left to right and the other will save from right to left.
 
Then we'll pop from the first array which will give nodes in right to left order.
If we pop the second arry, we'll get nodes from left to right order.
 

Order of appending and popping nodes

The order of saving and popping nodes will set whether if the current level is a zig or a zag.
 

1. Base Case & Initialization)

If the tree is empty, return an empty list.
 
Because we don't need to popleft for a zigzag pattern, we'll use lists instead of deque.
 
Variable zig is a list that will save nodes from right to left.
Variable zag is a list that will save nodes from left to right.
Variable res is a final list that will have lists of int of zigzagged nodes.
 
The reason why zig saves nodes from right to left is because we'll pop nodes. If we pop nodes, then the nodes will be in left to right order.
 
Append root in zig for its initial value.
 

def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 1.Base Case & Initialization
        if not root: return []

        zig, zag, res = [], [], []
        zig.append(root)

 

2. If zig traversal)

We'll iterate the entire tree until both zig and zag are empty.
 
Variable curr_lvl will save int vals of nodes from either zig or zag.
 
Consider a case where the current level is a zig pattern.
That will be when there are nodes in zig.
 
As said earlier, we'll pop nodes from zig to have nodes in left to right order.
Then we append their vals to curr_lvl.
 
After getting their values, we need to save their children. However, we'll save those children in zag because we need to save the children in zag pattern as our current pattern is zig. 
 
Save children from left to right.
 

def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 1.Base Case & Initialization
        if not root: return []

        zig, zag, res = [], [], []
        zig.append(root)

        # 2. If zig traversal
        while zig or zag:
            curr_lvl = []

            if zig:
                for _ in range(len(zig)):
                    cur = zig.pop()
                    curr_lvl.append(cur.val)

                    if cur.left: zag.append(cur.left)
                    if cur.right: zag.append(cur.right)

 

3. If zag traversal)

We'll take similar steps as we did with zig.
 
However, after we get the vals, we need to save the children nodes from right to left order in zig.
By saving children nodes in right to left order in zig, we can get their vals in left to right order when we pop them.
 
 
After getting values from either zig or zag, append that to res and repeat it for all the nodes. 
 

def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 1.Base Case & Initialization

        # 2. If zig traversal
        while zig or zag:
            curr_lvl = []

            if zig:
                for _ in range(len(zig)):
                    cur = zig.pop()
                    curr_lvl.append(cur.val)

                    if cur.left: zag.append(cur.left)
                    if cur.right: zag.append(cur.right)
            
            # 3. If zag traversal
            else:
                for _ in range(len(zag)):
                    cur = zag.pop()
                    curr_lvl.append(cur.val)

                    if cur.right: zig.append(cur.right)
                    if cur.left: zig.append(cur.left)

            res.append(curr_lvl)
        
        return res

---

 
 
 
Instead of this solution,  I kept reversing for zag pattern using reverse() function. I didn't like that I was wasting runtime, which seemed unnecessary. Then I swapped orders of popping and appending and got this solution.
 
 
I hope you have a breezy day 🌼