algoadvance

Given the root of 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).

Clarifying Questions

  1. What is the input format?
    • The input is a reference to the root of a binary tree.
  2. What is the output format?
    • The output should be a list of lists, where each sublist represents the values at each level from bottom to top.
  3. Are there any constraints on the tree size?
    • The number of nodes in the tree is in the range [0, 2000].
    • -1000 <= Node.val <= 1000
  4. Can the tree be empty?
    • Yes, the tree can be empty (i.e., root is None). In this case, the output should be an empty list.

Strategy

  1. Level Order Traversal: We will perform a standard level order traversal but insert the values at the beginning of our result list to achieve the bottom-up order.
  2. Queue: Use a queue to keep track of nodes at the current level.
  3. Reverse: Alternatively, collect the nodes’ values level by level and reverse the result list at the end.

Code

Let’s implement this in Python:

from collections import deque
from typing import List, Optional

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        
        result = []
        queue = deque([root])
        
        while queue:
            level_size = len(queue)
            current_level = []
            
            for _ in range(level_size):
                node = queue.popleft()
                current_level.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            result.insert(0, current_level)
        
        return result

# Example usage:
# Create a tree: 
#     3
#    / \
#   9  20
#     /  \
#    15   7
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

sol = Solution()
print(sol.levelOrderBottom(root))  # Output: [[15, 7], [9, 20], [3]]

Time Complexity

This solution ensures we are efficiently traversing and gathering values from the binary tree in the desired bottom-up level order.

Try our interview co-pilot at AlgoAdvance.com