LeetCode #102: Binary Tree Level Order Traversal

LeetCode Solutions

https://leetcode.com/problems/binary-tree-level-order-traversal/description/

To solve the problem, we will use a breadth-first search (BFS) approach. We will use a queue to keep track of the nodes in the tree that we have yet to visit. Starting with the root node, we will add it to the queue. Then, while the queue is not empty, we will remove the first node from the queue, add its value to the current level list, and add its left and right children to the queue if they exist. Once we have finished processing all the nodes in the current level, we add the current level list to the final result list.

Steps:

  1. Define a function levelOrder that takes the root node of the binary tree as input and returns a list of lists containing the values of nodes at each level of the tree.
  2. Create an empty list called ret_list to store the final result.
  3. Create a queue called que and add the root node to it.
  4. While the queue is not empty, do the following: a. Create an empty list called level to store the values of nodes at the current level. b. Iterate over all the nodes in the current level of the tree by using a loop that runs len(que) times. c. Remove the first node from the queue and store it in a variable called curr. d. If the current node curr is not None, add its value to the level list and add its left and right children to the que queue. e. If the level list is not empty, append it to the ret_list list.
  5. Return the ret_list list.

Here is the completed solution in Python3:

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        que = [root]
        ret_list = []
        while que:
            level = []
            for i in range(len(que)):
                curr = que.pop(0)
                if curr:
                    level.append(curr.val)
                    que.append(curr.left)
                    que.append(curr.right)
            if level:
                ret_list.append(level)
            
        return ret_list

Time Complexity: The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. This is because we need to visit each node exactly once.

Space Complexity: The space complexity of this algorithm is O(n), where n is the maximum number of nodes at any level of the binary tree. This is because we need to store all the nodes at each level in the queue before processing them.