Binary Tree Level Order Traversal (Leet Code-102)

This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 102. This is a Leet code problem named Binary Tree Level Order Traversal. We will solve it using python and it is the best space and time-optimized solution.

Question of Binary Tree Level Order Traversal

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

This type of searching is also Known as Breadth-first search (BFS). BFS is an algorithm for looking for nodes in a tree data structure that satisfy a specified property. Before moving on to the nodes at the next depth level, it begins at the root of the tree and investigates every node there. To keep track of the child nodes that were encountered but not yet visited, additional memory—typically a queue—is required.

Example

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2

Input: root = [1]
Output: [[1]]

Example 3

Input: root = []
Output: []

Constraints

The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000

Approach to solve Binary Tree Level Order Traversal

To solve this problem we will first create an empty queue. while traversing from top to bottom we store the left and right child of the node and do the same for them also.

Algorithm

This method performs the following steps for a given input array:

Check for the base case.
ret_lst – variable to store elements.
Create a variable queue to store elements while traversing.
level – to store the current level of the tree.
Repeat steps 6 to 16 for whole binary tree nodes.
qSize – variable to store the length of the queue.
append the return list to store elements of the current level.
Repeat steps 9 to 14 till qSize greater than zero.
pop the first element and store it in the temp variable.
Append ret_lst[level].append(temp.val).
If the left child exists then add it to the queue.
If the right child exists then add it to the queue.
decrease queue size by one.
End while
Increase the level
End While
Return ret_lst

Python Code for Binary Tree Level Order Traversal

# 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]]:

        #base case
        if root is None:
            return
        
        #variable to store elements
        ret_lst = []

        #queue to store elements while traversing
        queue = []
        #variable to track the current level of tree
        level = 0

        queue.append(root)
        
        #run for whole binary tree nodes
        while queue:
            #variable to store length of queue
            qSize = len(queue)
            #append the return list to store elements of current level
            ret_lst.append([])
            
            #run till qSize greater than zero
            while qSize > 0:    
                #pop the first element
                temp = queue.pop(0)
                ret_lst[level].append(temp.val)
                #if left child exists then add it
                if(temp.left):
                    queue.append(temp.left)
                #if right child exists then add it
                if(temp.right):
                    queue.append(temp.right)
                #decrease queue size by 1
                qSize -= 1
                 
            level+=1           
        return ret_lst