Binary Tree Level Order Traversal

mediumFREETreesBlind 75

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
-1000 <= Node.val <= 1000

Learn this in

Depth First Search & TreesDSA Study Plan Breadth First SearchDSA Study Plan

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

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.

Algorithm/Approach

The general approach to solve this problem involves using a queue data structure to keep track of the nodes at each level. The algorithm starts by adding the root node to the queue, then enters a loop that continues until the queue is empty. In each iteration of the loop, the algorithm removes all the nodes at the current level from the queue, adds their children to the queue, and prints the values of the nodes at the current level.

Step-by-Step Strategy

Here's a step-by-step breakdown of the solution:

Create an empty queue to store the nodes.
Add the root node to the queue.
While the queue is not empty:

Remove all the nodes at the current level from the queue.
Print the values of the nodes at the current level.
Add the children of the nodes at the current level to the queue.

Repeat step 3 until the queue is empty.

Common Pitfalls

Some common pitfalls to watch out for when implementing the solution include:

Forgetting to add the children of the nodes at the current level to the queue.
Not removing all the nodes at the current level from the queue before moving on to the next level.
Not handling the case where the input tree is empty.

Time & Space Complexity

The expected time complexity of the solution is $O(n)$ , where $n$ is the number of nodes in the tree, since each node is visited once. The expected space complexity is $O(n)$ , since in the worst case, the queue will store all the nodes at the last level of the tree.

solution.py

Python 3.13

Test results