Binary Tree Level Order Traversal I & II

Problem Statements I and II

Problem I Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).
Problem II Given the root of a binary tree, return the reverse level order traversal of its nodes’ values. (i.e., from left to right, level by level).

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

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

Example 2: Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -1000 <= Node.val <= 1000

Approach

We use BFS traversal.

What is level in our binary tree? It is set of nodes, for which distance between root and these nodes are constant. And if we talk about distances, it can be a good idea to use bfs.

We put our root into queue, now we have level 0 in our queue. On each step extract all nodes from queue and put their children to to opposite end of queue. In this way we will have full level in the end of each step and our queue will be filled with nodes from the next level. In the end we just return result.

Complexity: Time complexity is O(n), space complexity is O(n).

Solution for Problem I

def levelOrder(root):
    queue = deque([root])
    result = []

    while queue:
        level = []
        for i in range(len(queue)):
            curNode = queue.popleft()
            level.append(curNode.val)

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

        result.append(level)
    return result

Solution for Problem II

def levelOrder(root):
    queue = deque([root])
    result = []

    while queue:
        level = []
        for i in range(len(queue)):
            curNode = queue.popleft()
            level.append(curNode.val)

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

        result.append(level)
    return result[::-1]

Refrence

• FlyKiller