Binary Tree Level Order Traversal

easyPROTrees & SerializationDSA for AI Engineers

Given a binary tree (level-order array), return the level order traversal: the node values grouped by level, from the root level down, with each level's values in left-to-right order.

level_order(root) returns a list of lists, one inner list per level (an empty list for an empty tree). The tests print each level on a separate line, space-separated.

Example

Input

3,9,20,null,null,15,7

Output

3
9 20
15 7

Reasoning

The input 3,9,20,null,null,15,7 lists the tree top to bottom, left to right, with null marking a missing child. The root is 3; its children are 9 (left) and 20 (right); the two nulls say 9 has no children, so 15 and 7 are the left and right children of 20.
A node's level is its depth $d$ (edges from the root): $d(3)=0$ , $d(9)=d(20)=1$ , $d(15)=d(7)=2$ .
The traversal groups values by depth, one group for each $d = 0, 1, \dots, h$ , where $h$ is the tree's height. Here $h = 2$ , so there are $h + 1 = 3$ groups. Within a group, values keep their left-to-right order in the tree.
That gives the groups $[3]$ , $[9, 20]$ , $[15, 7]$ : a list of 3 lists. Printed one level per line, space-separated, they read 3, 9 20, 15 7.
Notice that 15 7 follows directly on the third line even though 9 has no children: missing nodes contribute nothing, leaving no gap. An empty tree has no levels, so its result is an empty list.

Constraints

0 <= number of nodes <= 2000

More from DSA for AI Engineers

Single Numbereasy Power of Twoeasy Flatten Binary Tree to Linked Listmedium Serialize and Deserialize Binary Treehard Coin Changemedium

Concept primerPREVIEW

Background Knowledge

The problem involves a binary tree, which is a data structure where each node has at most two children (i.e., left child and right child). In a binary tree, each level is fully filled before moving on to the next level, except for possibly the last level, which is filled from left to right. The level order traversal of a binary tree visits all the nodes at a given level before moving on to the next level. This type of traversal is also known as breadth-first traversal.

To understand the level order traversal, it's essential to know how a binary tree is represented. In this problem, the binary tree is given as a level-order array, where the nodes are arranged level by level, from left to right. For example, given a binary tree with the following structure:

The level-order array representation would be: [1, 2, 3, 4, 5, 6].

Background Knowledge: Key Concepts

Key concepts related to this problem include:

Binary Tree: A tree-like data structure where each node has at most two children.
Level Order Traversal: A traversal technique that visits all the nodes at a given level before moving on to the next level.
Breadth-First Traversal: Another name for level order traversal, which visits all the nodes at a given level before moving on to the next level.
Queue Data Structure: A data structure that follows the First-In-First-Out (FIFO) principle, which is often used to implement level order traversal.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results