Binary Tree Level Order Traversal II

Patrick Leaton
Published: April 3, 2021, 3:39 a.m.
Problem Description

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

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

    3
   / \
  9  20
    /  \
   15   7

 

return its bottom-up level order traversal as:

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

 

The description was taken from https://leetcode.com/problems/binary-tree-level-order-traversal-ii/.

Problem Solution

#O(N) Time, O(M) Space, where M is Max Nodes
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        queue = collections.deque()
        result = []
        if root is None:
            return result
        queue.append(root)
        while queue:
            bucket = []
            level_count = len(queue)
            for _ in range(level_count):
                node = queue.popleft()
                bucket.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(bucket)
        return result[::-1]

Problem Explanation

If we are doing a level order traversal, even for funky ones like this, a Breadth-First Search is typically our go-to solution.

All we need to do is traverse the tree from top to bottom, level by level, and before each level, we will grab a bucket, throw each node into the bucket then append the bucket to the output after we have traversed the level.  

Once we are done traversing the tree, we just need to reverse the output which will reverse the order of the buckets.

Let's start by initializing our queue and our result list.

        queue = collections.deque()
        result = []

 

If the input root is null, we will return an empty list.

        if root is None:
            return result

 

Otherwise, we will push the root node onto the queue.

        queue.append(root)

 

While we have nodes in our queue, we continue our level order traversal.

        while queue:

 

At the beginning of each level iteration, we will reset our bucket to be empty and also calculate the length of the queue.  This will give us how many nodes are at the current level.

            bucket = []
            level_count = len(queue)

 

We will then iterate through each node in the queue.

            for _ in range(level_count):

 

During each node iteration, we will pop the node from the queue and throw it into the bucket.

                node = queue.popleft()
                bucket.append(node.val)

 

Afterward, if the node has children then we will push those onto the queue so we can visit them at the next level.

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

 

Once we have traversed an entire level, we will append the bucket to the output.

            result.append(bucket)

 

Once we have appended each level's node values to our result, we will have a top-down level order traversal saved.

To get a bottom-up traversal, we will just need to reverse the buckets in the result array.

        return result[::-1]