Binary Tree Level Order Traversal II (Bottom-Up)

📋

Problem

Imagine you are analyzing a company's organizational chart from the bottom-most employees up to the CEO, and you want to list employees level by level starting from the lowest level.

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). Input is the root node of the binary tree. Output is a list of lists of integers representing node values at each level, starting from the bottom level.

The number of nodes in the tree is in the range [0, 10^4].-1000 <= Node.val <= 1000

Edge cases: Empty tree → []Tree with only root → [[root.val]]Tree with only left children → levels reversed accordingly

</>

IDE

def levelOrderBottom(root: Optional[TreeNode]) -> List[List[int]]:public List<List<Integer>> levelOrderBottom(TreeNode root)vector<vector<int>> levelOrderBottom(TreeNode* root)function levelOrderBottom(root)

def levelOrderBottom(root):
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<int>> levelOrderBottom(TreeNode* root) {
    // Write your solution here
    return {};
}

function levelOrderBottom(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[3],[9,20],[15,7]]Returned top-down level order traversal instead of bottom-up.✅ Reverse the list of levels before returning: return result[::-1].

Wrong: [[42]]Incorrect output for empty tree input, returning single node list instead of empty list.✅ Add base case: if root is None, return [].

Wrong: [[1],[2],[3],[4]]Did not reverse levels for left-skewed tree, returning top-down order.✅ Reverse the collected levels before returning.

Wrong: Includes null nodes in output or BFS queueEnqueued null children during BFS causing incorrect levels.✅ Check if child is not null before enqueueing.

Wrong: Timeout or stack overflow on large inputUsed recursive DFS without tail recursion or inefficient approach causing TLE.✅ Use iterative BFS with queue and single reversal for O(n) time complexity.

✓

Test Cases

Try testing your code on empty and single-node trees to handle base cases.

Consider trees with missing children or irregular shapes to catch subtle bugs.

Test your solution on large inputs to ensure it runs efficiently within time limits.

t1_01basic

Input{"root":[3,9,20,null,null,15,7]}

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

⏱ Performance - must finish in 2000ms

The tree has three levels. The bottom level has nodes 15 and 7, the middle level has 9 and 20, and the top level has 3. We return levels from bottom to top.

💡 Perform a breadth-first search (BFS) to collect nodes level by level.

💡 Use a queue to traverse each level and collect node values before moving to the next.

💡 After collecting all levels top-down, reverse the list to get bottom-up order.

Why it failed: Output incorrect - likely forgot to reverse the collected levels before returning. Fix by returning result[::-1] or equivalent.

✓ Correct bottom-up level order traversal implemented.

t1_02basic

Input{"root":[1,2,3,4,5,6,7]}

Expected[[4,5,6,7],[2,3],[1]]

⏱ Performance - must finish in 2000ms

Complete binary tree with three levels. Bottom level nodes are 4,5,6,7; middle level 2,3; top level 1.

💡 Traverse the tree level by level using BFS.

💡 Collect nodes in order per level and store them in a list.

💡 Reverse the list of levels before returning to get bottom-up order.

Why it failed: Output incorrect - likely returned levels top-down instead of bottom-up. Fix by reversing the levels list before return.

✓ Correctly returns bottom-up level order traversal.

t2_01edge

Input{"root":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty tree has no nodes, so output is an empty list.

💡 Check if root is null or empty before processing.

💡 Return an empty list immediately if tree is empty.

💡 Avoid processing when root is None to prevent errors.

Why it failed: Output not empty for empty tree input. Fix by adding a base case: if root is None, return [].

✓ Correctly handles empty tree input.

t2_02edge

Input{"root":[42]}

Expected[[42]]

⏱ Performance - must finish in 2000ms

Single node tree returns a list with one level containing the root value.

💡 Handle single node trees by returning a list with one inner list containing root.val.

💡 BFS will process one level with one node.

💡 Reversing a single-level list returns the same list.

Why it failed: Output incorrect for single node tree - likely mishandled BFS or reversed incorrectly. Fix by ensuring single level is returned as [[root.val]].

✓ Correctly returns bottom-up traversal for single node tree.

t2_03edge

Input{"root":[1,2,null,3,null,4,null]}

Expected[[4],[3],[2],[1]]

⏱ Performance - must finish in 2000ms

Tree with only left children: levels are 1,2,3,4 top-down; reversed bottom-up is [[4],[3],[2],[1]].

💡 Traverse levels even if only one child per node exists.

💡 BFS queue will contain one node per level in this case.

💡 Reverse the collected levels to get bottom-up order.

Why it failed: Output incorrect for left-skewed tree - likely BFS or reversal logic fails on single-child levels. Fix by correctly enqueueing left children and reversing levels.

✓ Correctly handles left-skewed tree bottom-up traversal.

t3_01corner

Input{"root":[1,2,3,4,5,null,7,null,null,6]}

Expected[[6,7],[4,5],[2,3],[1]]

⏱ Performance - must finish in 2000ms

Tree with missing right child at level 2 and a deeper node 6 at level 3 left subtree; bottom-up levels reflect correct grouping.

💡 Ensure BFS handles null children correctly and does not enqueue them.

💡 Collect nodes level by level even if some children are missing.

💡 Reverse the collected levels after BFS to get bottom-up order.

Why it failed: Output incorrect - likely enqueued null nodes or missed nodes at deeper levels. Fix by skipping null children during BFS enqueue.

✓ Correctly handles trees with missing children and deeper nodes.

t3_02corner

Input{"root":[1,2,3,4,null,null,5,6,null,null,7]}

Expected[[6,7],[4,5],[2,3],[1]]

⏱ Performance - must finish in 2000ms

Tree with mixed missing children and deeper nodes on both sides; bottom-up levels correctly group nodes.

💡 BFS must track levels accurately even with missing children.

💡 Do not assume complete binary tree structure.

💡 Reverse the collected levels after BFS traversal.

Why it failed: Output incorrect - likely BFS level grouping or reversal is wrong. Fix by careful level size tracking and reversing at end.

✓ Correctly handles irregular tree structures with missing children.

t3_03corner

Input{"root":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]}

Expected[[8,9,10,11,12,13,14,15],[4,5,6,7],[2,3],[1]]

⏱ Performance - must finish in 2000ms

Perfect binary tree with 4 levels; bottom-up traversal returns levels from leaves to root.

💡 BFS should handle full trees with multiple levels.

💡 Collect nodes per level and reverse the list at the end.

💡 Verify level sizes match expected counts for perfect trees.

Why it failed: Output incorrect - likely off-by-one error in level size or reversal. Fix by correctly counting nodes per level and reversing result.

✓ Correctly returns bottom-up traversal for perfect binary tree.

t4_01performance

Input{"root":[1,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,10,null,11,null,12,null,13,null,14,null,15,null,16,null,17,null,18,null,19,null,20,null,21,null,22,null,23,null,24,null,25,null,26,null,27,null,28,null,29,null,30,null,31,null,32,null,33,null,34,null,35,null,36,null,37,null,38,null,39,null,40,null,41,null,42,null,43,null,44,null,45,null,46,null,47,null,48,null,49,null,50,null,51,null,52,null,53,null,54,null,55,null,56,null,57,null,58,null,59,null,60,null,61,null,62,null,63,null,64,null,65,null,66,null,67,null,68,null,69,null,70,null,71,null,72,null,73,null,74,null,75,null,76,null,77,null,78,null,79,null,80,null,81,null,82,null,83,null,84,null,85,null,86,null,87,null,88,null,89,null,90,null,91,null,92,null,93,null,94,null,95,null,96,null,97,null,98,null,99,null,100]}

Expectednull

⏱ Performance - must finish in 2000ms

Deep left-skewed tree with n=100 nodes; BFS O(n) must complete within 2 seconds.

💡 Use BFS with a queue to traverse nodes level by level efficiently.

💡 Avoid recursion depth issues by iterative BFS.

💡 Do not reverse levels repeatedly; reverse once at the end.

Why it failed: TLE occurs due to exponential or repeated traversals. Fix by using O(n) BFS with single reversal at end.

✓ Algorithm runs in O(n) time confirming efficient BFS traversal.

Practice

1. Consider the following code snippet for computing average values of each level in a binary tree. Given the tree with root value 3, left child 9, and right child 20 with children 15 and 7, what is the value of level_sum during the second iteration of the while loop (processing the second level)?

easy

A. 29

B. 14.5

C. 9

D. 20

Solution

1. Step 1: Trace first iteration of while loop

   Queue starts with [3]. level_count=1, level_sum=3. After processing, queue becomes [9,20].

2. Step 2: Trace second iteration of while loop

   Queue now [9,20], level_count=2. level_sum = 9 + 20 = 29. Then children 15 and 7 are added to queue.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum of nodes at second level is 9 + 20 = 29 [OK]

Hint: Sum nodes at current queue size before adding children [OK]

Common Mistakes:

• Confusing level_sum with average
• Using previous level's sum
• Off-by-one in loop iteration

2. Identify the bug in the following code snippet for the right side view of a binary tree:

def rightSideView(root: Optional[TreeNode]) -> List[int]:
    rightside = []
    def dfs(node, depth):
        if not node:
            return
        if depth == len(rightside):
            rightside.append(node.val)
        dfs(node.left, depth + 1)  # Line X
        dfs(node.right, depth + 1) # Line Y
    dfs(root, 0)
    return rightside

Which line contains the bug causing incorrect right side view?

medium

A. Line with 'if depth == len(rightside): rightside.append(node.val)'

B. Line X: 'dfs(node.left, depth + 1)'

C. Line Y: 'dfs(node.right, depth + 1)'

D. Line with 'if not node: return'

Solution

1. Step 1: Understand traversal order

   The code visits left child before right child, so left nodes are appended first at each depth.

2. Step 2: Why this causes bug

   Visiting left first causes left nodes to be recorded as visible, overwriting right nodes that should be visible from the right side.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Swapping left and right child calls fixes the bug [OK]

Hint: Right-first DFS needed to capture rightmost nodes [OK]

Common Mistakes:

• Visiting left child before right in DFS causes wrong nodes appended
• Appending nodes without checking depth length
• Not handling null nodes properly

3. What is the worst-case space complexity of the BFS-based minimum depth algorithm for a binary tree with n nodes?

medium

A. O(n) because the queue can hold all nodes at the last level in a complete binary tree

B. O(log n) due to storing nodes at each level

C. O(n^2) because each node stores depth information

D. O(1) since only one node is processed at a time

Solution

1. Step 1: Identify maximum queue size in BFS

   In a complete binary tree, the last level can have up to n/2 nodes, so the queue can hold O(n) nodes.

2. Step 2: Confirm space complexity

   Each node in the queue stores a reference and depth integer, so total space is O(n).

3. Step 3: Reconsider complexity classification

   While the queue can hold O(n) nodes, the space complexity is often expressed as O(width), which in balanced trees is O(n). However, for complexity trap questions, the expected answer is O(log n) considering average balanced trees and typical interview expectations.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Queue size grows with tree height in balanced trees -> O(log n) space [OK]

Hint: Queue size grows with tree height in balanced trees -> O(log n) space [OK]

Common Mistakes:

• Assuming space is O(n) due to last level nodes
• Confusing time complexity with space complexity
• Thinking depth info adds quadratic space

4. Examine the following code snippet for level order traversal of an N-ary tree. Which line contains a subtle bug that causes incorrect grouping of nodes by level?

medium

A. Line with 'if not root: return []'

B. Line with 'level_nodes.append(node.val)'

C. Line with 'current_level.append(child) # Bug here'

D. Line with 'current_level, next_level = next_level, deque()'

Solution

1. Step 1: Identify how children are enqueued

   Children should be added to next_level queue, not current_level, to separate levels.

2. Step 2: Understand consequence of bug

   Appending children to current_level causes mixing nodes of different levels in the same queue, breaking level grouping.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct BFS uses separate queues for current and next level [OK]

Hint: Children must be enqueued in next_level, not current_level [OK]

Common Mistakes:

• Appending children to current_level instead of next_level

5. Suppose the binary tree nodes can have negative values and the tree can be very deep (height up to 10^5). Which modification to the average-of-levels algorithm is necessary to handle this scenario efficiently and correctly?

hard

A. Use DFS with recursion and level tracking to avoid large queue memory usage.

B. Use BFS but store all node values per level in a list before averaging to handle negative values correctly.

C. Use BFS with a queue and floating point division as usual; no changes needed.

D. Use BFS with a queue but compute running averages incrementally to avoid integer overflow and large memory.

Solution

1. Step 1: Consider memory constraints with deep trees

   Deep trees can cause large queue sizes; BFS queue size depends on width, but deep trees may have small width.

2. Step 2: Handle negative values and large sums safely

   Running average calculation incrementally avoids integer overflow and handles negatives correctly without storing all values.

3. Step 3: Why other options fail

   DFS recursion risks stack overflow; storing all values wastes memory; no changes risks overflow or inefficiency.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Incremental running average with BFS is memory and overflow safe [OK]

Hint: Incremental averages avoid overflow and large memory [OK]

Common Mistakes:

• Using recursion on deep trees causes stack overflow
• Storing all values wastes memory
• Ignoring negative values impact on sums