Binary Tree Level Order Traversal

▶

Steps

setup

Initialize result list and start DFS at root

We initialize an empty list 'result' to hold nodes values by level. Then we start the DFS recursion at the root node (3) at level 0.

💡 Starting with an empty result is essential to build the level order lists dynamically as we visit nodes.

Line:

result = []
dfs(root, 0)

💡 The recursion begins at the root with level 0, setting the stage for level-based grouping.

fill_row

Add new level list for level 0 and append root value

Since level 0 equals the length of result (which is 0), we append a new empty list to result. Then we add the root node's value (3) to this list.

💡 Adding a new list for a new level ensures nodes are grouped correctly by their depth.

Line:

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

💡 The algorithm dynamically creates a list for each new level encountered during recursion.

traverse

Recurse into left child (9) at level 1

We recursively call dfs on the left child node (9) with level incremented to 1.

💡 Recursing left first follows the depth-first order and explores the next level.

Line:

dfs(node.left, level + 1)

💡 The recursion moves down one level, preparing to add values to the next level list.

fill_row

Add new level list for level 1 and append value 9

Since level 1 equals the length of result (1), we append a new empty list. Then we add node 9's value to this new list.

💡 Each new level encountered triggers creation of a new list to hold that level's nodes.

Line:

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

💡 The algorithm builds the result list incrementally as it discovers deeper levels.

traverse

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

We recursively call dfs on the left child of node 9, which is null, at level 2. Since the node is null, the recursion returns immediately.

💡 Handling null nodes correctly prevents errors and stops recursion down empty branches.

Line:

if not node:
    return

💡 Null children do not add values or levels, so recursion stops here.

traverse

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

We recursively call dfs on the right child of node 9, which is also null, at level 2. The recursion returns immediately again.

💡 Both children of leaf nodes are null, so recursion ends at these points.

Line:

if not node:
    return

💡 Leaf nodes have no children to add, so recursion backtracks.

traverse

Return from node 9 and recurse into right child (20) at level 1

Having finished both children of node 9, recursion returns to node 0 and now calls dfs on the right child node (20) at level 1.

💡 After finishing left subtree, recursion explores right subtree at the same level.

Line:

dfs(node.right, level + 1)

💡 The algorithm explores all nodes at each level by visiting left then right children recursively.

fill_row

Append value 20 to existing level 1 list

Since level 1 is already in result, we append node 20's value to the existing list for level 1.

💡 Nodes at the same level are grouped together in the same list.

Line:

result[level].append(node.val)

💡 The algorithm accumulates all nodes at a level in one list, preserving order of visitation.

traverse

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

We recursively call dfs on node 20's left child (15) at level 2.

💡 Moving deeper into the tree, recursion explores the next level nodes.

Line:

dfs(node.left, level + 1)

💡 The recursion continues to build the result for deeper levels.

fill_row

Add new level list for level 2 and append value 15

Since level 2 equals the length of result (2), we append a new empty list. Then we add node 15's value to this new list.

💡 New levels trigger new lists to hold their nodes' values.

Line:

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

💡 The algorithm builds the result list level by level as recursion deepens.

traverse

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

We recursively call dfs on node 15's left child, which is null, at level 3. The recursion returns immediately.

💡 Null children end recursion branches safely.

Line:

if not node:
    return

💡 Leaf nodes have no children, so recursion backtracks here.

traverse

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

We recursively call dfs on node 15's right child, which is null, at level 3. The recursion returns immediately.

💡 Both children of leaf nodes are null, ending recursion branches.

Line:

if not node:
    return

💡 Recursion backtracks after visiting all children of a leaf node.

traverse

Return from node 15 and recurse into right child (7) of node 20 at level 2

After finishing node 15, recursion returns to node 20 and calls dfs on its right child (7) at level 2.

💡 Recursion explores all children of a node before returning.

Line:

dfs(node.right, level + 1)

💡 The algorithm visits all nodes at a level before backtracking.

fill_row

Append value 7 to existing level 2 list

Since level 2 already exists in result, we append node 7's value to the existing list for level 2.

💡 Nodes at the same level are collected together in order of visitation.

Line:

result[level].append(node.val)

💡 The algorithm maintains order of nodes within each level.

traverse

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

We recursively call dfs on node 7's left child, which is null, at level 3. The recursion returns immediately.

💡 Null children end recursion branches safely.

Line:

if not node:
    return

💡 Leaf nodes have no children, so recursion backtracks here.

traverse

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

We recursively call dfs on node 7's right child, which is null, at level 3. The recursion returns immediately.

💡 Both children of leaf nodes are null, ending recursion branches.

Line:

if not node:
    return

💡 Recursion backtracks after visiting all children of a leaf node.

return

Return from node 20 and then from root node 3

Having visited all children of node 20, recursion returns to root node 3, then finally returns from root after completing traversal.

💡 Recursion unwinds after all nodes are visited, returning the final result.

Line:

return result

💡 The entire tree has been traversed and the result list is complete.

from typing import List, Optional

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

def dfs_level_order(root: Optional[TreeNode]) -> List[List[int]]:
    result = []  # STEP 1: Initialize result list
    def dfs(node: Optional[TreeNode], level: int):
        if not node:  # STEP 5,6,11,12,15,16: Return on null node
            return
        if level == len(result):  # STEP 2,4,10: Add new list for new level
            result.append([])
        result[level].append(node.val)  # STEP 2,4,8,10,14: Append node value to level list
        dfs(node.left, level + 1)  # STEP 3,5,9,11,15: Recurse left child
        dfs(node.right, level + 1)  # STEP 7,6,12,13,16: Recurse right child
    dfs(root, 0)  # STEP 1: Start DFS at root
    return result  # STEP 17: Return final result

# Example usage:
# root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
# print(dfs_level_order(root))

📊

Binary Tree Level Order Traversal - Watch the Algorithm Execute, Step by Step

Watching the recursion and level tracking live reveals how the algorithm builds the level order result without explicit queues, making the process intuitive.

Current node: 0

3920157

DFS Stack

0 (entered)level=0

Current node: 0

3920157

DFS Stack

0 (left_done)level=0

Result: [3]

Current node: 1

3920157

DFS Stack

1 (entered)level=10 (left_done)level=0

Result: [3]

Current node: 1

3920157

DFS Stack

1 (left_done)level=10 (left_done)level=0

Result: [3, 9]

3920157

DFS Stack

null (entered)level=21 (left_done)level=10 (left_done)level=0

Result: [3, 9]

3920157

DFS Stack

null (entered)level=21 (right_done)level=10 (left_done)level=0

Result: [3, 9]

Current node: 2

3920157

DFS Stack

2 (entered)level=10 (right_done)level=0

Result: [3, 9]

Current node: 2

3920157

DFS Stack

2 (left_done)level=10 (right_done)level=0

Result: [3, 9,20]

Current node: 3

3920157

DFS Stack

3 (entered)level=22 (left_done)level=10 (right_done)level=0

Result: [3, 9,20]

Current node: 3

3920157

DFS Stack

3 (left_done)level=22 (left_done)level=10 (right_done)level=0

Result: [3, 9,20, 15]

3920157

DFS Stack

null (entered)level=33 (left_done)level=22 (left_done)level=10 (right_done)level=0

Result: [3, 9,20, 15]

3920157

DFS Stack

null (entered)level=33 (right_done)level=22 (left_done)level=10 (right_done)level=0

Result: [3, 9,20, 15]

Current node: 4

3920157

DFS Stack

4 (entered)level=22 (right_done)level=10 (right_done)level=0

Result: [3, 9,20, 15]

Current node: 4

3920157

DFS Stack

4 (left_done)level=22 (right_done)level=10 (right_done)level=0

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

3920157

DFS Stack

null (entered)level=34 (left_done)level=22 (right_done)level=10 (right_done)level=0

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

3920157

DFS Stack

null (entered)level=34 (right_done)level=22 (right_done)level=10 (right_done)level=0

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

3920157

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

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

Key Takeaways

✓ The recursion uses level tracking to group nodes by depth without explicit queues.

This insight is hard to see from code alone because recursion and level tracking interplay subtly to build the result.

✓ New lists are created dynamically only when a new level is first encountered.

Watching this happen live clarifies how the algorithm avoids preallocating or guessing tree height.

✓ Null nodes immediately return, preventing unnecessary processing and ensuring correct traversal.

Seeing recursion return on null nodes helps understand how leaf nodes terminate recursion branches.

Practice

1. Consider the following code snippet implementing the optimal approach to find the maximum width of a binary tree. Given the tree below: 1 / \ 3 2 / \ 5 9 What is the value of max_width returned by the function?

easy

A. 3

B. 2

C. 4

D. 5

Solution

1. Step 1: Trace first level

   Root node 1 at index 0; max_width updated to 1.

2. Step 2: Trace second level

   Nodes 3 and 2 at indices 0 and 1 (after normalization). Width = 1 - 0 + 1 = 2.

3. Step 3: Trace third level

   Nodes 5 and 9 at indices 0 and 3 (after normalization). Width = 3 - 0 + 1 = 4.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Maximum width is 4 at the last level [OK]

Hint: Normalize indices per level to compute width correctly [OK]

Common Mistakes:

• Not normalizing indices before computing width
• Counting nodes instead of width including null gaps
• Off-by-one error in width calculation

2. You are given a binary tree where each node may have zero, one, or two children. Your task is to connect each node's next pointer to its next right node on the same level. If there is no next right node, the next pointer should be set to NULL. Which approach guarantees an optimal solution with O(n) time and O(h) space, where h is the tree height?

easy

A. Use a dynamic programming approach to store connections and build them bottom-up.

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

C. Use a recursive top-down approach that leverages already established next pointers to connect nodes without extra queue space.

D. Apply a greedy approach that connects nodes as soon as they are discovered during DFS.

Solution

1. Step 1: Understand the problem constraints

   The problem requires connecting next pointers in any binary tree, not necessarily perfect or complete, with O(n) time and O(h) space.

2. Step 2: Evaluate approaches

   Using a queue (Perform a level order traversal using a queue to connect nodes level by level.) uses O(n) space, violating the space constraint. DP (Use a dynamic programming approach to store connections and build them bottom-up.) is not applicable here. Greedy DFS (Apply a greedy approach that connects nodes as soon as they are discovered during DFS.) fails to guarantee correct connections across siblings at the same level. The recursive top-down approach (Use a recursive top-down approach that leverages already established next pointers to connect nodes without extra queue space.) uses existing next pointers to traverse levels efficiently with O(h) recursion stack space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Top-down recursion with next pointers -> O(n) time, O(h) space [OK]

Hint: Top-down recursion uses next pointers to avoid extra space [OK]

Common Mistakes:

• Assuming BFS with queue is optimal space-wise
• Trying DP bottom-up which doesn't fit this problem
• Using DFS greedily without next pointers

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

4. Suppose the binary tree can have nodes with duplicate values and you want to return the right side view but also include all nodes visible from the right side at each depth (not just the first). Which modification to the optimal DFS approach correctly handles this variant?

hard

A. Use DFS with right-first traversal but overwrite the node value at each depth to keep the last visited node.

B. Use BFS level order traversal and collect the last node at each level only.

C. Change DFS to visit left child first and append all nodes at each depth to a list.

D. Modify DFS to visit right child first and append every node encountered at each depth to a list instead of only the first.

Solution

1. Step 1: Understand requirement

   We want all nodes visible from the right side at each depth, not just the first.

2. Step 2: Modify DFS to collect all nodes per depth

   Visiting right child first ensures rightmost nodes are visited first, but we must append every node at that depth to a list, not just the first.

3. Step 3: Why other options fail

   Left-first traversal or overwriting values loses rightmost visibility; BFS collecting only last node misses duplicates.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Right-first DFS appending all nodes per depth captures all visible nodes [OK]

Hint: Right-first DFS appending all nodes per depth [OK]

Common Mistakes:

• Using left-first traversal loses rightmost nodes
• Appending only first or last node per depth misses duplicates
• Overwriting values loses multiple visible nodes

5. Suppose the problem is extended so that the tree nodes can have multiple children (not just binary), and you need to check if the tree is symmetric around its center. Which modification to the BFS approach is necessary to correctly handle this case?

hard

A. Enqueue children in normal order and compare corresponding children pairs directly

B. Enqueue children in mirrored order and compare pairs from opposite ends of the children list

C. Use a recursive approach only, as BFS cannot handle multiple children

D. Check symmetry only at the root level and ignore deeper levels

Solution

1. Step 1: Understand symmetry in multi-child trees

   Symmetry means the first child on the left subtree mirrors the last child on the right subtree, second mirrors second last, etc.

2. Step 2: Modify BFS to enqueue children in mirrored order

   Enqueue children pairs from opposite ends of the children list to compare mirrored positions correctly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Mirrored enqueue order for multiple children preserves symmetry checks [OK]

Hint: Multi-child symmetry requires mirrored child pair comparisons [OK]

Common Mistakes:

• Enqueuing children in normal order causing false positives
• Assuming BFS cannot be adapted for multi-child trees
• Ignoring deeper levels of the tree