< Back





102. Binary Tree Level Order Traversal

Return the level order traversal of a binary tree. Pretty straightfoward, just conduct BFS.

The solution is as follows:


  class Solution:
      def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
          if not root:
              return []

          ans = []
          queue = [root]

          while queue:
              curr_queue, queue = queue, []
              level = []

              for node in curr_queue:
                  if node:
                      level.append(node.val)

                      if node.left:
                          queue.append(node.left)
                      if node.right:
                          queue.append(node.right)

              ans.append(level)

          return ans


_ Time Complexity:

  O(n) - We traverse O(n) nodes of the tree.

_ Space Complexity:

  O(n) - The queue can contain at most O(n) nodes of the tree.