Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. Level order traversal means traversing the tree level by level, from left to right.

Function Signature:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order_traversal(root: TreeNode) -> List[List[int]]:
    """
    Perform level order traversal on a binary tree.

    Parameters:
    - root: The root of the binary tree.

    Returns:
    - List[List[int]]: A list of lists containing the values of nodes at each level.
    """
    # Your code here

Example:

# Example Binary Tree:
#        3
#       / \
#      9  20
#        /  \
#       15   7

root = TreeNode(3, 
	            TreeNode(9), 
	            TreeNode(20, 
	            	     TreeNode(15), 
	            	     TreeNode(7)
	            	     )
	            )

result = level_order_traversal(root)
print(result)
assert result == [[3], [9, 20], [15, 7]]
# Explanation: Level 1 is the root [3]. Level 2 is [9, 20]. And level 3 is [15, 7]

Note:

• The given binary tree is not necessarily a binary search tree.
• All node values are unique.

Instructions:

• Write the level_order_traversal function to solve the problem.
• Implement your solution in Python.
• Provide clear comments in your code.
• Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊