Binary Tree Level Order Traversal II

Given a binary tree, return its level order traversal where the nodes in each level are ordered from left to right, and the levels are ordered from bottom to top.

Example(s)

Example 1:

Tree:
    2
   / \
  1   2
Output: [[1,2],[2]]

Example 2:

Tree:
    7
   / \
  6   2
 / \
3   3
Output: [[3,3],[6,2],[7]]

Solution

JavaScript Solution

JavaScript Bottom-Up Level Order Traversal Solution

/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/

/**
* Perform bottom-up level order traversal of a binary tree
* @param {TreeNode} root - Root of the binary tree
* @return {number[][]} - Bottom-up level order traversal result
*/
function levelOrderBottom(root) {
if (!root) return [];

const result = [];
const queue = [root];

while (queue.length) {
  const levelSize = queue.length;
  const currentLevel = [];
  
  for (let i = 0; i < levelSize; i++) {
    const node = queue.shift();
    currentLevel.push(node.val);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  
  result.unshift(currentLevel);
}

return result;
}

// Test case 1: [2,1,2]
const tree1 = new TreeNode(2);
tree1.left = new TreeNode(1);
tree1.right = new TreeNode(2);

// Test case 2: [7,6,2,3,3]
const tree2 = new TreeNode(7);
tree2.left = new TreeNode(6);
tree2.right = new TreeNode(2);
tree2.left.left = new TreeNode(3);
tree2.left.right = new TreeNode(3);

// Test cases
console.log(levelOrderBottom(tree1)); // [[1,2],[2]]
console.log(levelOrderBottom(tree2)); // [[3,3],[6,2],[7]]
console.log(levelOrderBottom(null)); // []

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Bottom-Up Level Order Traversal Solution

from typing import Optional, List
from collections import deque

# 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

def level_order_bottom(root: Optional[TreeNode]) -> List[List[int]]:
  """
  Perform bottom-up level order traversal of a binary tree
  
  Args:
      root: Root of the binary tree
      
  Returns:
      List[List[int]]: Bottom-up level order traversal result
  """
  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

# Test case 1: [2,1,2]
tree1 = TreeNode(2)
tree1.left = TreeNode(1)
tree1.right = TreeNode(2)

# Test case 2: [7,6,2,3,3]
tree2 = TreeNode(7)
tree2.left = TreeNode(6)
tree2.right = TreeNode(2)
tree2.left.left = TreeNode(3)
tree2.left.right = TreeNode(3)

# Test cases
print(level_order_bottom(tree1))  # [[1,2],[2]]
print(level_order_bottom(tree2))  # [[3,3],[6,2],[7]]
print(level_order_bottom(None))  # []

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Complexity

• Time Complexity: O(n) - Where n is the number of nodes in the tree
• Space Complexity: O(n) - For the queue and result storage

Approach

The solution uses a breadth-first search (BFS) approach with a queue:

1. Initialize an empty result array and a queue with the root node
2. Process each level by:
   • Determining the current level size
   • Processing all nodes at the current level
   • Adding their children to the queue for the next level
3. Insert each level at the beginning of the result array using unshift() (JavaScript) or insert(0, ...) (Python)
4. Return the result array

Key Insights

• Breadth-first search ensures level-by-level traversal
• Queue data structure efficiently processes nodes in order
• Reverse order achieved by inserting levels at the beginning of the result
• Edge cases include empty tree, single-node tree, and single-level trees
• O(n) time is optimal as all nodes must be visited