4          <- level 0
      /   \
     2     5       <- level 1
    / \
   1   3            <- level 2

BFS visit order: 4 → 2 → 5 → 1 → 3
(visit all nodes on one level before moving to the next)

Sol 1: BFS Iterative
1. if not root: 
        a. return []
2. (groups = [])
3. (queue = deque([root]))
4. while queue:
   a. depthLevelSize = len(queue)
   b. level = []
   c. for _ in range(depthLevelSize):
        node = queue.popleft()
        level.append(node.val)
        if node.left: 
            queue.append(node.left)
        if node.right: 
            queue.append(node.right)
   d. groups.append(level)
5. return groups

Sol 2: DFS Pre Order Recursive
1. (groups = [])
2. dfs(node, depth):
   a. if not node: 
        return
   b. if len(groups) == depth: 
        groups.append([])
   c. groups[depth].append(node.val)
   d. dfs(node.left, depth + 1)
   e. dfs(node.right, depth + 1)
3. dfs(root, 0)
4. return groups

    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        
        # Note:
        # BFS level order: process nodes level by level, 
        # (left -> right) within each level

        # Empty check:
        # Tree is empty, return empty list
        if not root:
            return []
        
        # List of groups by level
        groups = []

        # Iterative queue for BFS:
        # holds nodes to process, starting with root as first level
        # sc: O(n)
        queue = deque([root])
        
        # tc: O(n)
        while queue:

            # Number of nodes remaining in deque,
            # which represent the nodes at the current depth level
            depthLevelSize = len(queue)

            # List of nodes at current level
            level = []
            
            # For the number of nodes remaining in deque and this level,
            # pop and process each node in this level
            for _ in range(depthLevelSize):

                # FIFO: pop leftmost node from queue and process
                node = queue.popleft()
                level.append(node.val)
                
                # after processing, enqueue children for next level,
                # to represent the next level of the tree for BFS
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            # Add nodes at current level to 
            groups.append(level)
        
        # overall: tc O(n)
        # overall: sc O(n)
        return groups

    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        
        # Note:
        # DFS pre order: root -> left -> right
        # 1. Create list of groups by depth level
        # 2. Process root and track current depth level during traversal
        #    and add node to corresponding depth group
        
        # Depth level groups
        # sc: O(n)
        groups = []
        
        def dfs(node, depth):

            # Empty check:
            # Reached leaf, return
            if not node:
                return
            
            # Check:
            # if next depth level has been reached, add a new group
            if len(groups) == depth:
                groups.append([])
            
            # For each node we encounter, add its value for pre order
            # to the corresponding depth group
            groups[depth].append(node.val)
            
            # Track current depth level and recurse to children
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)
        
        # Start at root, start depth at 0
        dfs(root, 0)

        # overall: tc O(n)
        # overall: sc O(n)
        return groups

Sol 1: BFS And BFS Pruning Optimization
1. if not root: 
    return []
2. (queue = deque([root]))
3. (reverseFlag = True)
4. (groups = [])
5. while queue:
    a. depthLevelSize = len(queue)
    b. group = []
    c. for _ in range(depthLevelSize):
         node = queue.popleft()
         group.append(node.val)
         if node.left: 
             queue.append(node.left)
         if node.right: 
             queue.append(node.right)
    d. if reverseFlag:
         res.append(group)
    e. else:
         groups.append(group[::-1])
    f. reverseFlag = not reverseFlag
6. return groups

    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        
        # Note:
        # BFS level order + zigzag
        # 1. Standard BFS level traversal, always append left -> right (natural order)
        # 2. To create a zig zag effect, 
        #    reverse the completed level list when direction is right -> left

        # Empty check:
        if not root:
            return []

        # Iterative BFS Queue
        queue = deque([root])

        # Reverse flag used to flip every iteration
        reverseFlag = True

        # zig zagged groups
        groups = []

        # tc: O(n)
        while queue:

            # Number of nodes remaining at this depth level
            depthLevelSize = len(queue)

            # Nodes at this depth level
            group = []

            for _ in range(depthLevelSize):
                node = queue.popleft()

                # Always append normally
                group.append(node.val)

                # Normal BFS expansion (unaffected by direction)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            # Reverse the queue to apply zigzag effect
            if reverseFlag:
                groups.append(group)
            else:
                groups.append(group[::-1])

            # Flip reveres flag for next iteration
            reverseFlag = not reverseFlag

        # overall: tc O(n)
        # overall: sc O(n)
        return groups