102. Binary Tree Level Order Traversal

Problem

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example: Given binary tree [3,9,20,null,null,15,7],

3 / \ 9 20 / \ 15 7

return its level order traversal as:

[ [3], [9,20], [15,7] ]

Thought Process

  • This is a typical BFS problem
  • Can solve it with the help of a queue
  • In Python, can use collection.deque for queue

Code

# Definition for a binary tree node.
from collections import deque
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def levelOrder(self, root):
        # initialization
        res = [[]] # a list of list
        q = deque()
        level = 0 # store the level info
        curr = (root, level)
        q.append(curr) #append both node and its level

        # if the tree is empty
        if root is None:
            return []

        # loop as long as q has element
        while q:
            curr = q.popleft()
            node, level = curr[0], curr[1]

            if level == len(res):
                # level should be 1 less than the length of result
                # if level equals the len of result, need to start a new array for new level
                res.append([])

            res[level].append(node.val)

            if node.left:
                q.append((node.left, level+1))

            if node.right:
                q.append((node.right, level+1))

        return res        

Complexity

  • Time complexity is O(n), a while loop is used
  • Space complexity is also O(n), a deque is used to store node and its level info

White Board

Below is the white board:

Optimization

How to improve?