🦄 Canopy Walk: Level Order Traversal

Difficulty: Intermediate Tags: trees, bfs, queue, level-order Series: Data Structures I

Problem

Imagine walking through a forest canopy, level by level, from top to bottom. That's exactly what we're doing with a binary tree!

Your task: Given a binary tree in array format, return its level-order traversal - which means visiting all nodes level by level, from left to right.

What's a Binary Tree?

A binary tree is a data structure where each node has: - A value - At most two children: left and right

Think of it like a family tree, but each person can have max 2 children.

Input

data = {
    'nodes': list[list[int, int, int]],  # Array representation of tree
    'root': int                           # Index of root node
}

How nodes work: Each node is [value, left_child_index, right_child_index] - First number = the node's value - Second number = index of left child (-1 if no left child) - Third number = index of right child (-1 if no right child)

Output

list[list[int]]  # List of levels, each level is a list of values

Constraints

• Number of nodes ≤ 100,000
• -1 means "no child here" (null)

Examples

Example: A Small Tree

Input:
{
    'nodes': [[3,1,2], [9,-1,-1], [20,3,4], [15,-1,-1], [7,-1,-1]],
    'root': 0
}

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

Let's break this down step by step:

The Tree Structure:

      3           ← Level 0 (root)
     / \
    9   20        ← Level 1
       /  \
     15    7      ← Level 2

Understanding the nodes array: - Index 0: [3, 1, 2] → Node 3 has left child at index 1, right child at index 2 - Index 1: [9, -1, -1] → Node 9 has no children (it's a leaf) - Index 2: [20, 3, 4] → Node 20 has left child at index 3, right child at index 4 - Index 3: [15, -1, -1] → Node 15 has no children - Index 4: [7, -1, -1] → Node 7 has no children

Level-by-level traversal: - Level 0: Start at root (index 0) → value is 3 - Level 1: Children of 3 → indices 1 and 2 → values are 9 and 20 - Level 2: Children of 9 (none) and children of 20 → indices 3 and 4 → values are 15 and 7

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

Example: Empty Tree

Input:  {'nodes': [], 'root': -1}
Output: []

If there's no tree (root is -1), return an empty list.