#102. Binary Tree Level Order Traversal | LeetCode Python Solution

Problem

LeetCode Problem

102. Binary Tree Level Order Traversal

Python Solution

# 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: Optional[TreeNode]) -> List[List[int]]:
        # Return an empty list if root node is null
        if not root:
            return []

        # Create an empty queue and enqueue the root node
        q = deque()
        q.append(root)

        # Create an output list to collect level's node list
        output = []

        # Loop until the queue is empty
        while q:
            # Create a level list to collect nodes in the current level
            level = []

            # Process each node in the queue for the current level
            # Enqueue their non-empty left and right child node
            for _ in range(len(q)):
                node = q.popleft()
                level.append(node.val)

                if node.left:
                    q.append(node.left)

                if node.right:
                    q.append(node.right)

            # Add the current level's nodes as a list to output list
            output.append(level)

        return output

Big O Notation:

Time Complexity:

O(n) | Where n is the number of nodes in our binary tree | As we have to traverse all of the nodes within the tree.

Space Complexity:

O(q) | Where q is the length of the Queue we use to perform level order traversal of the binary tree