Binary Tree Level Order Traversal

from collections import deque

# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
        # Handle empty root case
        if not root:
            return []

        result = []

        # Breadth first search
        q = deque([(root, 0)])

        # Keep track of previous node length to track when we reach a new depth
        prevnode_depth = -1

        # Store values in current level
        level_values = []

        while len(q) > 0:
            currnode_tuple = q.popleft()
            currnode = currnode_tuple[0]
            currnode_depth = currnode_tuple[1]

            # If level_values is empty, add currnode
            if len(level_values) == 0:
                level_values.append(currnode.val)

            # Else if the currnode is at same level, add currnode val to level_values
            elif currnode_depth == prevnode_depth:
                level_values.append(currnode.val)

            # Else if currnode is not at the same level
            else:
                # Add level values to result
                result.append(level_values)
                # Reset level values
                level_values = [currnode.val]

            # Append currnode's children to BFS
            if currnode.left:
                q.append((currnode.left, currnode_depth + 1))
            if currnode.right:
                q.append((currnode.right, currnode_depth + 1))

            prevnode_depth = currnode_depth

        # Return result array
        result.append(level_values)
        return result