N-ary Tree Level Order Traversal

▶

Steps

setup

Initialize result and queues

We start by checking if the root exists. Since it does, we initialize the result list and put the root node (1) into the current_level queue.

💡 Setting up the queues is essential to start the BFS traversal from the root.

Line:

res = []
current_level = deque([root])
next_level = deque()

💡 The traversal begins at the root node, which is the first level.

fill_row

Start processing level 0

We begin processing the first level by initializing an empty list to hold node values of this level.

💡 Collecting node values per level is the core of level order traversal.

Line:

level_nodes = []

💡 We prepare to gather all nodes at the current level before moving on.

fill_cells

Process node 1 at level 0

We dequeue node 1 from current_level, add its value to level_nodes, and enqueue its children (3, 2, 4) to next_level.

💡 Processing each node involves recording its value and preparing its children for the next level.

Line:

node = current_level.popleft()
level_nodes.append(node.val)
for child in node.children:
    next_level.append(child)

💡 Children of the current node are queued for processing in the next iteration, ensuring level order.

fill_row

Finish level 0 and add to result

All nodes at level 0 are processed, so we add the collected values [1] to the result list and prepare to process the next level by swapping queues.

💡 Adding the level list to the result preserves the order of levels in the output.

Line:

res.append(level_nodes)
current_level, next_level = next_level, deque()

💡 Swapping queues moves the traversal focus to the next level of nodes.

fill_row

Start processing level 1

We initialize an empty list to collect values of nodes at level 1 before processing them.

💡 Each level starts with an empty list to gather node values.

Line:

level_nodes = []

💡 This prepares the algorithm to process all nodes at the current level.

fill_cells

Process node 3 at level 1

We dequeue node 3, add its value to level_nodes, and enqueue its children (5, 6) to next_level for the next level processing.

💡 Processing children nodes prepares the next level's queue.

Line:

node = current_level.popleft()
level_nodes.append(node.val)
for child in node.children:
    next_level.append(child)

💡 Children of node 3 are added to the next level queue, expanding the traversal frontier.

fill_cells

Process node 2 at level 1

We dequeue node 2, add its value to level_nodes. Node 2 has no children, so next_level remains unchanged.

💡 Nodes without children do not add new nodes to the next level queue.

Line:

node = current_level.popleft()
level_nodes.append(node.val)
for child in node.children:
    next_level.append(child)

💡 Leaf nodes contribute only their value to the current level list.

fill_cells

Process node 4 at level 1

We dequeue node 4, add its value to level_nodes. Node 4 has no children, so next_level remains unchanged.

💡 Processing the last node at this level completes the current level's node collection.

Line:

node = current_level.popleft()
level_nodes.append(node.val)
for child in node.children:
    next_level.append(child)

💡 All nodes at level 1 are now processed, and their children are queued for the next level.

fill_row

Finish level 1 and add to result

We add the collected values [3, 2, 4] of level 1 to the result list and swap queues to process the next level.

💡 Adding the level list to the result preserves the order of levels in the output.

Line:

res.append(level_nodes)
current_level, next_level = next_level, deque()

💡 Swapping queues moves the traversal focus to the next level of nodes.

fill_row

Start processing level 2

We initialize an empty list to collect values of nodes at level 2 before processing them.

💡 Each level starts with an empty list to gather node values.

Line:

level_nodes = []

💡 This prepares the algorithm to process all nodes at the current level.

fill_cells

Process node 5 at level 2

We dequeue node 5, add its value to level_nodes. Node 5 has no children, so next_level remains empty.

💡 Leaf nodes contribute only their value to the current level list.

Line:

node = current_level.popleft()
level_nodes.append(node.val)
for child in node.children:
    next_level.append(child)

💡 Leaf nodes do not add new nodes to the next level queue.

fill_cells

Process node 6 at level 2

We dequeue node 6, add its value to level_nodes. Node 6 has no children, so next_level remains empty.

💡 Processing the last node at this level completes the current level's node collection.

Line:

node = current_level.popleft()
level_nodes.append(node.val)
for child in node.children:
    next_level.append(child)

💡 All nodes at level 2 are now processed, and no further nodes remain to process.

fill_row

Finish level 2 and add to result

We add the collected values [5, 6] of level 2 to the result list. Since no nodes remain in current_level, the traversal ends.

💡 Adding the last level completes the full level order traversal result.

Line:

res.append(level_nodes)

💡 The BFS traversal completes when no more nodes remain to process.

reconstruct

Return final result

The traversal is complete, so we return the accumulated result containing all levels: [[1], [3, 2, 4], [5, 6]].

💡 Returning the result concludes the BFS level order traversal.

Line:

return res

💡 The final output is a list of lists, each representing a level of the tree.

from collections import deque

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

def levelOrder(root):
    if not root:
        return []  # STEP 1: Check root
    res = []  # STEP 1: Initialize result
    current_level = deque([root])  # STEP 1: Initialize current_level queue
    next_level = deque()  # STEP 1: Initialize next_level queue
    while current_level:  # STEP 3: While current_level not empty
        level_nodes = []  # STEP 2: Initialize level_nodes list
        while current_level:  # STEP 3 inner loop: process all nodes in current_level
            node = current_level.popleft()  # STEP 3: Dequeue node
            level_nodes.append(node.val)  # STEP 3: Add node value
            for child in node.children:  # STEP 4: Enqueue children
                next_level.append(child)
        res.append(level_nodes)  # STEP 4: Add level_nodes to result
        current_level, next_level = next_level, deque()  # STEP 5: Swap queues
    return res  # STEP 6: Return final result

if __name__ == '__main__':
    root = Node(1, [Node(3, [Node(5), Node(6)]), Node(2), Node(4)])
    print(levelOrder(root))

📊

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

Watching this step-by-step traversal reveals how breadth-first search explores nodes level by level, which is hard to grasp from code alone.

132456

BFS Queue

N1 (L0)

Current node: 1

132456

BFS Queue

N1 (L0)

132456

BFS Queue

N2 (L1)N3 (L1)N4 (L1)

132456

BFS Queue

N2 (L1)N3 (L1)N4 (L1)

Result: [1]

Current node: 2

132456

BFS Queue

N2 (L1)N3 (L1)N4 (L1)

Result: [1]

132456

BFS Queue

N3 (L1)N4 (L1)

Result: [1]

132456

BFS Queue

N4 (L1)

Result: [1]

132456

Result: [1]

132456

BFS Queue

N5 (L2)N6 (L2)

Result: [1, 3,2,4]

Current node: 5

132456

BFS Queue

N5 (L2)N6 (L2)

Result: [1, 3,2,4]

132456

BFS Queue

N6 (L2)

Result: [1, 3,2,4]

132456

Result: [1, 3,2,4]

132456

Result: [1, 3,2,4, 5,6]

132456

Result: [1, 3,2,4, 5,6]

Return: [[1],[3,2,4],[5,6]]

Key Takeaways

✓ Level order traversal uses queues to process nodes breadth-first, level by level.

This insight is hard to see from code alone because the queue operations and level boundaries are implicit.

✓ Children of all nodes at the current level are collected before moving to the next level.

Visually seeing children queued for the next level clarifies the dependency between levels.

✓ Traversal ends when no nodes remain in the current level queue, ensuring all levels are processed.

Understanding the termination condition is easier when watching the empty queue signal the end.

Practice

1. Consider the following Python code implementing the optimal DFS approach for bottom-up level order traversal. What is the final output when run on the given tree?

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

def levelOrderBottom(root):
    levels = []
    def dfs(node, level):
        if not node:
            return
        if len(levels) == level:
            levels.append([])
        levels[level].append(node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return levels[::-1]

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20, TreeNode(15), TreeNode(7))
print(levelOrderBottom(root))

easy

A. [[15, 7], [9, 20], [3]]

B. [[3], [9, 20], [15, 7]]

C. [[9, 20], [3], [15, 7]]

D. [[15, 7], [3], [9, 20]]

Solution

1. Step 1: Trace dfs calls and levels

   Level 0: [3], Level 1: [9, 20], Level 2: [15, 7]

2. Step 2: Reverse levels list before returning

   Reversing [[3], [9, 20], [15, 7]] yields [[15, 7], [9, 20], [3]]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches bottom-up level order traversal [OK]

Hint: Remember to reverse levels collected by DFS [OK]

Common Mistakes:

• Forgetting to reverse levels
• Mixing up left and right children order

2. Given a binary tree and two node values, you need to determine if these nodes are at the same depth but have different parents. Which algorithmic approach best guarantees an optimal solution for this problem?

easy

A. Breadth-first search (BFS) level order traversal to check nodes level by level

B. Dynamic programming to store subtree information and compare nodes

C. Depth-first search (DFS) separately to find depth and parent of each node

D. Greedy approach to pick nodes based on immediate parent comparison

Solution

1. Step 1: Understand problem constraints

   The problem requires checking if two nodes are at the same depth and have different parents, which naturally aligns with level-based traversal.

2. Step 2: Identify algorithm suitability

   BFS level order traversal processes nodes level by level, allowing simultaneous checking of node parents and depths in O(n) time, making it optimal.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS directly accesses nodes by level, perfect for cousin checks [OK]

Hint: Level order traversal matches level-based cousin checks [OK]

Common Mistakes:

• Using DFS twice separately wastes time
• Greedy misses depth checks
• DP is unnecessary overhead

3. What is the time complexity of the optimal DFS approach for bottom-up level order traversal of a binary tree with n nodes?

medium

A. O(n log n) due to reversing the levels list at the end

B. O(n) for traversal plus O(h) for recursion stack space, where h is tree height

C. O(n) because each node is visited exactly once and reversal is O(n)

D. O(n^2) because appending to levels at each depth can be costly

Solution

1. Step 1: Analyze DFS traversal cost

   Each node is visited once, so traversal is O(n).

2. Step 2: Analyze reversal cost

   Reversing the levels list is O(L), where L ≤ n (number of levels), so O(n) worst case.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Traversal plus reversal both linear in n [OK]

Hint: DFS visits each node once; reversal is linear [OK]

Common Mistakes:

• Confusing reversal cost as O(n log n)
• Assuming quadratic due to nested lists

4. What is the time complexity of the BFS level order traversal approach used to determine if two nodes in a binary tree are cousins, assuming the tree has n nodes?

medium

A. O(n^2) because each level is processed separately

B. O(n log n) due to repeated queue operations

C. O(n) because each node is visited exactly once

D. O(h) where h is the height of the tree due to level traversal

Solution

1. Step 1: Identify BFS traversal cost

   BFS visits each node once, enqueuing and dequeuing each node exactly one time.

2. Step 2: Analyze per-node operations

   Each node's children are checked once, so total operations scale linearly with n.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear traversal over all nodes confirms O(n) time [OK]

Hint: BFS visits each node once, so O(n) time [OK]

Common Mistakes:

• Confusing BFS with DFS recursion stack cost
• Assuming repeated level processing causes O(n^2)
• Mistaking height for total nodes

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