Binary Tree Level Order Traversal II (Bottom-Up)

▶

Steps

setup

Initialize levels list and start DFS at root level 0

We create an empty list 'levels' to hold node values per level. Then we call dfs on the root node (value 3) at level 0.

💡 Initializing 'levels' is essential to store nodes grouped by their depth. Starting DFS at root level 0 sets the base for level tracking.

Line:

levels = []
dfs(root, 0)

💡 The algorithm will build the levels list dynamically as it visits nodes at increasing depths.

fill_row

Create level 0 list and append root value

Since levels list is empty, we add a new list for level 0. Then we append the root node's value (3) to levels[0].

💡 Creating a new list for the current level ensures nodes are grouped correctly by depth.

Line:

if len(levels) == level:
    levels.append([])
levels[level].append(node.val)

💡 Levels list grows dynamically as deeper levels are reached during DFS.

traverse

Recurse into left child (node 9) at level 1

We call dfs on the left child of node 3, which is node 9, increasing the level to 1.

💡 Moving to the left child explores the next node at a deeper level, tracking level + 1.

Line:

dfs(node.left, level + 1)

💡 DFS explores left subtree first, maintaining level tracking for grouping.

fill_row

Create level 1 list and append node 9 value

Since levels has only one list, we add a new list for level 1. Then append node 9's value to levels[1].

💡 Adding a new list for level 1 groups all nodes at this depth together.

Line:

if len(levels) == level:
    levels.append([])
levels[level].append(node.val)

💡 Levels list now has two lists: top level and next level nodes.

traverse

Recurse into left child of node 9 (null) at level 2

Node 9 has no left child, so dfs is called with None and level 2, which immediately returns.

💡 Handling null children prevents errors and ends recursion branches correctly.

Line:

if not node:
    return
dfs(node.left, level + 1)

💡 Null children are base cases that stop recursion.

traverse

Recurse into right child of node 9 (null) at level 2

Node 9 has no right child, so dfs is called with None and level 2, which immediately returns.

💡 Both children being null means node 9 is a leaf, so recursion returns to parent.

Line:

dfs(node.right, level + 1)

💡 Leaf nodes end recursion branches after both children are processed.

returning

Return from node 9 DFS call to node 3

Both children of node 9 processed, so dfs call for node 9 returns to node 3's context.

💡 Returning from recursion means finishing processing a subtree and continuing traversal.

Line:

return

💡 DFS backtracks after finishing left subtree to explore right subtree.

fill_row

Append node 20 value to existing level 1 list

Level 1 list already exists, so we append node 20's value to levels[1], which currently has [9].

💡 Appending to existing level list groups all nodes at the same depth together.

Line:

levels[level].append(node.val)

💡 Multiple nodes at the same level are collected in the same list.

traverse

Recurse into left child of node 20 (node 15) at level 2

We call dfs on node 20's left child, node 15, increasing level to 2.

💡 Moving deeper into the tree explores the next level of nodes.

Line:

dfs(node.left, level + 1)

💡 DFS continues to explore left subtree first at the next level.

fill_row

Create level 2 list and append node 15 value

Levels list has only two lists, so we add a new list for level 2 and append node 15's value.

💡 Creating a new list for the deeper level groups leaf nodes correctly.

Line:

if len(levels) == level:
    levels.append([])
levels[level].append(node.val)

💡 Levels list now has three lists, one per tree depth.

traverse

Recurse into left child of node 15 (null) at level 3

Node 15 has no left child, so dfs is called with None and level 3, returning immediately.

💡 Null children end recursion branches cleanly.

Line:

if not node:
    return
dfs(node.left, level + 1)

💡 Leaf nodes have null children that stop recursion.

traverse

Recurse into right child of node 15 (null) at level 3

Node 15 has no right child, so dfs is called with None and level 3, returning immediately.

💡 Both children null means leaf node processing is complete.

Line:

dfs(node.right, level + 1)

💡 Leaf node recursion ends after both children are processed.

returning

Return from node 15 DFS call to node 20

Both children of node 15 processed, so dfs call returns to node 20's context.

💡 Returning from recursion means finishing a subtree and continuing traversal.

Line:

return

💡 DFS backtracks after finishing left subtree to explore right subtree.

traverse

Recurse into right child of node 20 (node 7) at level 2

We call dfs on node 20's right child, node 7, increasing level to 2.

💡 Exploring the right subtree completes the traversal of node 20's children.

Line:

dfs(node.right, level + 1)

💡 DFS explores all children at the current level before returning.

fill_row

Append node 7 value to existing level 2 list

Level 2 list exists, so we append node 7's value to levels[2], which currently has [15].

💡 Appending groups all nodes at the same depth together.

Line:

levels[level].append(node.val)

💡 All nodes at level 2 are collected in the same list.

traverse

Recurse into left child of node 7 (null) at level 3

Node 7 has no left child, so dfs is called with None and level 3, returning immediately.

💡 Null children end recursion branches cleanly.

Line:

if not node:
    return
dfs(node.left, level + 1)

💡 Leaf nodes have null children that stop recursion.

traverse

Recurse into right child of node 7 (null) at level 3

Node 7 has no right child, so dfs is called with None and level 3, returning immediately.

💡 Both children null means leaf node processing is complete.

Line:

dfs(node.right, level + 1)

💡 Leaf node recursion ends after both children are processed.

returning

Return from node 7 DFS call to node 20

Both children of node 7 processed, so dfs call returns to node 20's context.

💡 Returning means finishing processing of a subtree.

Line:

return

💡 DFS backtracks after finishing right subtree to complete node 20 processing.

reconstruct

Return from root DFS call and reverse levels list

DFS traversal is complete. We reverse the levels list to get bottom-up order: [[15,7],[9,20],[3]].

💡 Reversing the collected levels produces the required bottom-up traversal output.

Line:

return levels[::-1]

💡 The final answer is the reversed levels list, showing nodes from bottom to top.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrderBottom(root):
    levels = []  # STEP 1: Initialize levels list
    def dfs(node, level):
        if not node:  # STEP 5,6,11,12,16,17: Base case for null nodes
            return
        if len(levels) == level:  # STEP 2,4,10: Create new level list if needed
            levels.append([])
        levels[level].append(node.val)  # STEP 2,4,8,10,15: Append node value to level list
        dfs(node.left, level + 1)  # STEP 3,5,9,11,16: Recurse left child
        dfs(node.right, level + 1)  # STEP 6,12,14,17: Recurse right child
    dfs(root, 0)  # STEP 1: Start DFS at root level 0
    return levels[::-1]  # STEP 19: Reverse levels for bottom-up order

if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(levelOrderBottom(root))

📊

Binary Tree Level Order Traversal II (Bottom-Up) - Watch the Algorithm Execute, Step by Step

Watching each recursive call and how levels are tracked reveals how DFS can be adapted to level order traversal, which is often done with BFS. This approach is elegant and efficient.

Current node: 0

3920157

DFS Stack

0 (entered)level=0

Current node: 0

3920157

DFS Stack

0 (entered)level=0 levels=[[3]]

Result: [3]

Current node: 1

3920157

DFS Stack

1 (entered)level=1 levels=[[3]]0 (left_done)level=0 levels=[[3]]

Result: [3]

Current node: 1

3920157

DFS Stack

1 (entered)level=1 levels=[[3],[9]]0 (left_done)level=0 levels=[[3],[9]]

Result: [3, 9]

3920157

DFS Stack

1 (entered)level=1 levels=[[3],[9]]0 (left_done)level=0 levels=[[3],[9]]

Result: [3, 9]

3920157

DFS Stack

1 (right_done)level=1 levels=[[3],[9]]0 (left_done)level=0 levels=[[3],[9]]

Result: [3, 9]

Current node: 2

3920157

DFS Stack

2 (entered)level=1 levels=[[3],[9]]0 (right_done)level=0 levels=[[3],[9]]

Result: [3, 9]

Current node: 2

3920157

DFS Stack

2 (entered)level=1 levels=[[3],[9,20]]0 (right_done)level=0 levels=[[3],[9,20]]

Result: [3, 9,20]

Current node: 3

3920157

DFS Stack

3 (entered)level=2 levels=[[3],[9,20]]2 (left_done)level=1 levels=[[3],[9,20]]0 (right_done)level=0 levels=[[3],[9,20]]

Result: [3, 9,20]

Current node: 3

3920157

DFS Stack

3 (entered)level=2 levels=[[3],[9,20],[15]]2 (left_done)level=1 levels=[[3],[9,20],[15]]0 (right_done)level=0 levels=[[3],[9,20],[15]]

Result: [3, 9,20, 15]

3920157

DFS Stack

3 (entered)level=2 levels=[[3],[9,20],[15]]2 (left_done)level=1 levels=[[3],[9,20],[15]]0 (right_done)level=0 levels=[[3],[9,20],[15]]

Result: [3, 9,20, 15]

3920157

DFS Stack

3 (right_done)level=2 levels=[[3],[9,20],[15]]2 (left_done)level=1 levels=[[3],[9,20],[15]]0 (right_done)level=0 levels=[[3],[9,20],[15]]

Result: [3, 9,20, 15]

Current node: 2

3920157

DFS Stack

2 (left_done)level=1 levels=[[3],[9,20],[15]]0 (right_done)level=0 levels=[[3],[9,20],[15]]

Result: [3, 9,20, 15]

Current node: 4

3920157

DFS Stack

4 (entered)level=2 levels=[[3],[9,20],[15]]2 (right_done)level=1 levels=[[3],[9,20],[15]]0 (right_done)level=0 levels=[[3],[9,20],[15]]

Result: [3, 9,20, 15]

Current node: 4

3920157

DFS Stack

4 (entered)level=2 levels=[[3],[9,20],[15,7]]2 (right_done)level=1 levels=[[3],[9,20],[15,7]]0 (right_done)level=0 levels=[[3],[9,20],[15,7]]

Result: [3, 9,20, 15,7]

3920157

DFS Stack

4 (entered)level=2 levels=[[3],[9,20],[15,7]]2 (right_done)level=1 levels=[[3],[9,20],[15,7]]0 (right_done)level=0 levels=[[3],[9,20],[15,7]]

Result: [3, 9,20, 15,7]

3920157

DFS Stack

4 (right_done)level=2 levels=[[3],[9,20],[15,7]]2 (right_done)level=1 levels=[[3],[9,20],[15,7]]0 (right_done)level=0 levels=[[3],[9,20],[15,7]]

Result: [3, 9,20, 15,7]

Current node: 0

3920157

DFS Stack

0 (returning)level=0 levels=[[3],[9,20],[15,7]]

Result: [3, 9,20, 15,7]

3920157

Result: [3, 9,20, 15,7]

Return: [[15,7],[9,20],[3]]

Key Takeaways

✓ DFS can be adapted to perform level order traversal by tracking levels during recursion.

This insight is hard to see from code alone because DFS is usually associated with preorder/inorder/postorder, not level order.

✓ The levels list grows dynamically as deeper levels are reached, grouping nodes by their depth.

Visualizing the dynamic creation of level lists clarifies how nodes are grouped without BFS queues.

✓ Reversing the collected levels after DFS completes produces the bottom-up order required by the problem.

Understanding the final reversal step is easier when you see the levels built top-down first.

Practice

1. You are given a perfect binary tree where each node has two children. The task is to connect each node's next pointer to its immediate right neighbor on the same level, or NULL if there is none. Which approach guarantees an optimal solution with O(1) extra space and O(n) time complexity?

easy

A. Use the already established next pointers to traverse each level and connect children without extra space.

B. Perform a level order traversal using a queue to connect nodes at each level.

C. Apply a dynamic programming approach to store and connect nodes level-wise.

D. Use a depth-first search recursion to connect nodes from top to bottom.

Solution

1. Step 1: Understand the problem constraints

   The tree is perfect, so every node has two children, and all leaves are at the same level.

2. Step 2: Identify the approach that uses constant extra space

   Using next pointers already set on the current level to connect the next level avoids extra data structures like queues.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Optimal approach uses existing pointers to traverse levels [OK]

Hint: Use next pointers to traverse levels without extra space [OK]

Common Mistakes:

• Assuming BFS with queue is optimal space-wise
• Confusing DFS recursion with constant space
• Using DP which is unrelated

2. You are given a binary tree and need to determine if it is symmetric around its center. Which approach best guarantees an optimal solution by comparing nodes in pairs using a queue and terminating early when asymmetry is detected?

easy

A. Recursive depth-first traversal comparing left subtree to left subtree

B. Dynamic programming storing subtree symmetry states bottom-up

C. Greedy traversal checking only the root and immediate children

D. Iterative breadth-first search using a queue to compare mirrored node pairs with early termination

Solution

1. Step 1: Understand the problem requirement

   The problem requires checking if a tree is symmetric, which means the left subtree is a mirror reflection of the right subtree.

2. Step 2: Identify the approach that compares mirrored nodes efficiently

   Using an iterative BFS with a queue to compare pairs of nodes from left and right subtrees simultaneously allows early detection of asymmetry and avoids unnecessary traversal.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Iterative BFS with paired nodes and early termination is optimal for symmetry check [OK]

Hint: Symmetry requires mirrored node pair comparison [OK]

Common Mistakes:

• Comparing left subtree to left subtree instead of mirrored right subtree
• Using greedy checks that miss deeper asymmetry
• Assuming symmetry can be checked by root and immediate children only

3. What is the time and space complexity of the optimal DFS approach for the binary tree right side view problem, where the tree has n nodes and height h?

medium

A. Time: O(n), Space: O(h)

B. Time: O(h), Space: O(h)

C. Time: O(n), Space: O(n)

D. Time: O(n log n), Space: O(n)

Solution

1. Step 1: Identify time complexity

   The DFS visits each node exactly once, so time complexity is O(n).

2. Step 2: Identify space complexity

   Space is dominated by recursion stack, which is at most the height h of the tree, so O(h).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DFS recursion stack space depends on tree height, not total nodes [OK]

Hint: DFS time O(n), space O(tree height) [OK]

Common Mistakes:

• Assuming space is O(n) due to storing output or recursion stack
• Confusing time complexity with BFS level order traversal
• Thinking recursion stack is O(n log n) due to tree balancing

4. What is the space complexity of the optimal recursive approach to connect next right pointers in any binary tree, considering the recursion stack and auxiliary variables?

medium

A. O(h) where h is the height of the tree, due to recursion stack depth.

B. O(n) because each node is visited once and recursion stack can grow to n in skewed trees.

C. O(1) constant space since no extra data structures are used.

D. O(n) because the algorithm uses a queue internally to traverse levels.

Solution

1. Step 1: Identify recursion stack usage

   The recursion calls traverse right then left child, so the maximum depth of recursion is the height h of the tree.

2. Step 2: Check auxiliary space

   No extra data structures like queues are used, only a few pointers and variables, so auxiliary space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Space dominated by recursion stack -> O(h) [OK]

Hint: Recursion stack space equals tree height, not total nodes [OK]

Common Mistakes:

• Confusing recursion stack with queue space
• Assuming constant space despite recursion
• Thinking worst case is always O(n) for space

5. If the binary tree is not perfect (some nodes may have only one child or none), which modification to the algorithm is necessary to correctly populate next right pointers?

hard

A. Use a queue for level order traversal to handle missing children explicitly.

B. Keep using the next pointer traversal but add checks to find the next available child at the same level.

C. Use recursion only on left children since right children may be missing.

D. No modification needed; the original algorithm works for any binary tree.

Solution

1. Step 1: Understand why the original algorithm fails on non-perfect trees

   It assumes every node has both left and right children, so direct connections fail if children are missing.

2. Step 2: Identify the correct modification

   Traverse using next pointers but add logic to find the next available child on the same level to connect properly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Handling missing children requires scanning next pointers for available nodes [OK]

Hint: Scan next pointers to find next child when children missing [OK]

Common Mistakes:

• Assuming perfect tree always
• Using naive BFS with extra space
• Ignoring missing children causes bugs