Leetcode 102. Binary Tree Level Order Traversal

Problem

Leetcode 102 - Binary Tree Level Order Traversal

Example:

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

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

Input: root = []
Output: []

Approach

We can use Breadth First Search so we can return the array of array with level.

Here is the Python code for the solution:

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        q = deque()
        q.append(root)

        while q:
            level = []
            for _ in range(len(q)):
                curr = q.popleft()
                level.append(curr.val)
                if curr.left:
                    q.append(curr.left)
                if curr.right:
                    q.append(curr.right)
            
            res.append(level)
        return res

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(1)$