We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Tree Level Order Traversal II

Difficulty: Medium

Problem Description

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).

Key Insights

  • We need to traverse the tree level by level but collect the values in reverse order.
  • A breadth-first search (BFS) approach can be utilized using a queue to assist in level order traversal.
  • We can store the results in a temporary list and then reverse it before returning.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the binary tree, as we visit each node once.

Space Complexity: O(n) - for storing the result of the traversal, and O(w) for the queue, where w is the maximum width of the tree.

Solution

To solve the problem, we can use a breadth-first search (BFS) approach using a queue. We will enqueue the root node and begin traversing the tree level by level. For each level, we will collect the values of the nodes in a temporary list. Once we have traversed all levels, we will reverse the temporary list to achieve the bottom-up order before returning it.

Code Solutions

from collections import deque

def levelOrderBottom(root):
    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.append(current_level)
    
    return result[::-1]
← Back to All Questions