Binary Tree Level Order Traversal Ii - Leetcode Solution

Problem Statement:

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

Solution:

We can solve this problem using BFS (Breadth First Search) algorithm. We can start by pushing the root node into a queue. Then we can iterate through each level of the tree by popping each node from the queue. We can push the child nodes of each popped node to the queue. We can also keep track of the current level and add all the nodes' values of the current level to a list. We can repeat this process until the queue becomes empty.

After completing the traversal, we can reverse the list of nodes' values to get the bottom-up level order traversal.

Let's look at the implementation of the solution:

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        # initialize empty queue and result list
        queue = []
        res = []
        
        if not root:
            return res
        
        # push the root node to the queue
        queue.append(root)
        
        while queue:
            # get the number of nodes in the current level
            level_size = len(queue)
            
            # initialize a list to store the nodes' values of the current level
            level_nodes = []
            
            # iterate through each node of the current level
            for i in range(level_size):
                # remove the first node from the queue
                node = queue.pop(0)
                
                # append the node's value to the list
                level_nodes.append(node.val)
                
                # push the node's child nodes to the queue
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            # append the nodes' values of the current level to the result list
            res.append(level_nodes)
        
        # reverse the result list to get the bottom-up level order traversal
        res.reverse()
        
        return res

Time Complexity:

The time complexity of the BFS algorithm is O(n), where n is the number of nodes in the binary tree.

Space Complexity:

The space complexity of the BFS algorithm is O(n), where n is the number of nodes in the binary tree. The space is used to store the queue and the result list.

1