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])  # start with root
        
        # 
        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)
        
        dfs(root, 0)

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

    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        
        # Note:
        # BFS pre order: process level : root -> left -> right
        # 1. For each level
        # 2. Process root -> :
        #    grab length of level, if root is last element in group, add to res
        # 3. Process -> left -> right :
        # Result: right most element of each level added
        
        # Empty check:
        # No rightmost to return, return empty list
        if not root:
            return []
        
        # List of the right most element for each level
        res = []
        
        # Iterative BFS queue
        queue = deque([root])
        
        while queue:

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

            # For the number of nodes remaining in deque and this level,
            # pop and process each node in this level
            for i in range(depthLevelSize):

                # Grab the leftmost node from queue and process
                node = queue.popleft()

                # Check:
                # Validate if this node is the right most at this level
                if i == depthLevelSize - 1:
                    res.append(node.val)

                # Queue children for processing later
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        # overall: tc O(n)
        # overall: sc O(n)
        return res

    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        
        # Note:
        # DFS Modified Pre Order: (root -> right -> left) instead of (root -> left -> right)
        # Modified pre order goes root -> right, which guarantees we explore
        # the farthest right possible, before exploring left, 
        # and with that assumption, every time we reach a new depth,
        # we are guaranteed to be at the right most element for that depth level

        # Tracking right most elements for each level
        # sc: O(n)
        res = []
        
        def dfs(node, depth):

            # Empty check:
            # Reached leaf, return
            if not node:
                return

            # Check:
            # If we have reached a new depth, using our assumption of
            # (root -> right -> left), we can guarantee that we are at the right most node
            # for this level, and can add it to our right most list 
            if depth == len(result):
                res.append(node.val)

            # Modified Pre Order:
            # Explore right subtree first, then left subtree
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)
        
        # Init depth tracker at 0
        dfs(root, 0)

        # overall: tc O(n)
        # overall: sc O(n) for skewed trees / O(log(n)) for balanced trees
        return res

    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:
        # tree is empty
        if not root:
            return []

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

        # Reverse flag used to determine if we need to flip this iteration
        reverseFlag = True

        # zig zagged groups
        res = []

        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 reverse flag is on
            res.append(group if reverseFlag else group[::-1])

            # Flip reveres flag for next iteration
            reverseFlag = not reverseFlag

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

    def openLock(self, deadends: List[str], target: str) -> int:
        
        # BFS over the lock's state graph

        # Each 4-digit combination is represented as a node in an implicit graph,
        # meaning there is no literal grid/list to build, 
        # but instead states are generated on the fly.
        # An edge connects two states if one wheel-turn transforms one into another,
        # as each of the 4 wheels can turn +1 or -1 with wraparound 0 <-> 9
        # BFS explores states level by level, so the first time a 'target' is dequeued,
        # it is guaranteed to be the shortest number of turns
        

        # Dead end states set
        # sc: O(n)
        dead = set(deadends)
        
        # Edge Case:
        # If starting position is a dead end, we cannot move.
        if "0000" in dead:
            return -1
        
        # Iterative BFS Queue:
        # set starting position as "0000" as begin exploring
        queue = deque([("0000", 0)])
        visited = set(["0000"])
        
        while queue:

            # Pop a state from the queue
            state, moves = queue.popleft()
            
            # Check:
            # if target reached, we are guaranteed to have minimum number of moves
            if state == target:
                return moves
            
            # Explore Neighbors:
            # turn all 4 wheels in +/- 1 directions
            for i in range(4):

                # pick 1 of the 4 wheels
                digit = int(state[i])
                
                # Two possible rotations:
                # +1 and -1 (with wraparound)
                for change in (-1, 1):
                    
                    new_digit = (digit + change) % 10
                    
                    # Grab original wheel digits, 
                    # except for the one we just rotated
                    newState = (state[:i] + str(new_digit) + state[i+1:])
                    
                    # Early Pruning:
                    # only queue state if:
                    # - not visited
                    # - not a dead end
                    if newState not in visited and newState not in dead:
                        
                        visited.add(newState)
                        queue.append((newState, moves + 1))

        # Exhausted all possible rotation combinations without finding target

        # overall: tc O(10^4)
        # overall: sc O(10^4)
        return -1

    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        
        # BFS over the gene mutation graph

        # Each gene string combination is represented as a node in an implicit graph,
        # meaning there is no literal grid/list to build, 
        # but instead states are generated on the fly.
        # An edge connects two states if one gene slot modification transforms
        # one into another, as there are 4 possible gene letters.
        # BFS explores states level by level, so the first time a 'target' is dequeued,
        # it is guaranteed to be the shortest number of turns
        # as well as guaranteed to have all possible gene combinations
        
        
        # Turn valid gene list into set
        # sc: O(n)
        bankSet = set(bank)

        # Edge Case:
        # endGene is not reachable
        if endGene not in bankSet:
            return -1

        # All gene slot chars
        gene_chars = ['A', 'C', 'G', 'T']

        # Iterative BFS Queue
        queue = deque([(startGene, 0)])

        # Tracking 
        # sc: O(n^4)
        visited = {startGene}

        while queue:
            geneString, mutations = queue.popleft()

            # Reached target gene:
            # Ensured we have taken the minimum number of steps to get to
            # the final combination, which implies we have all possible previous 
            # combinations in the mutations list
            if geneString == endGene:
                return mutations

            # Modify each gene slot
            for i in range(len(geneString)):

                # Explore Neighbor:
                # Replace each gene slot with all other 3 genes
                for c in gene_chars:

                    # Skip original gene
                    if c == geneString[i]:
                        continue

                    # Grab all original gene slots, 
                    # except for the slot we just modified
                    rotatedGene = geneString[:i] + c + geneString[i + 1:]

                    # Early Pruning:
                    # Only queue mutations that are valid (in bank) and unseen
                    if rotatedGene in bankSet and rotatedGene not in visited:
                        visited.add(rotatedGene)
                        queue.append((rotatedGene, mutations + 1))

        # Exhausted all reachable mutations without finding endGene

        # overall: tc O(n)
        # overall: sc O(n)
        return -1