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

LeetCode 102

This problem just simply the implementation of the level order traversal algorithm. If you don’t know about level order traversal yet, you can check my blog on this topic.

As we know, using level order traversal, we traverse through the tree level by level. But in this problem, we have to separate values of each level instead of just plain print.

                                    1
                                 /     \
                                2       3
                              /   \    /   \
                             4     5  6     7

The problem detail is simple. If we take the above binary tree as an example, the answer will be: [[1], [2, 3], [4, 5, 6, 7]]. Each of the levels we will store in a different array.

Let’s see the code for a better understanding.

# 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]]:
        
        if not root:
            return []
        
        queue = deque()
        queue.append(root)
        
        res = []
        
        while queue:
            
            level = []
            for _ in range(len(queue)):
                
                node = queue.popleft()
                level.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                
            res.append(level)
        
        return res

As we know, we need a queue for this algorithm. If there is no root, we return an empty array. Otherwise, we add it to the Queue.

And then we run a loop till it’s become empty. The important part is inside this loop. Inside this loop, we run another one, which will define the level. Think about our above tree. Initially, we have only the root node(1) in the Queue. So it will run for one time. During that time, we add its children to the Queue. And store the root node value in an array for the final result. After that, we append this level to the final result and go back to the parent loop. It will run again because the Queue (2, 3) is not empty.

This time, the inside loop runs two times. Because from the previous level, we got only two nodes. Those are 2, 3. And then, we add these two nodes’ children to the Queue and store these two nodes in an array for the final result. And we remove these nodes from the Queue before adding their children. These two nodes are the level-2 nodes of the tree if we count the root as level-1.

And we do this again and again until the Queue is not empty. After all of it, we will return the final result.

Time Complexity O(n)
Space Complexity O(n)

I hope the code explained it better than my explanation.