Binary Tree Level Order Traversal
title: Binary Tree Level Order Traversal tags: levelordertreetraversal recursion queue
Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Example 2:
Input: root = [1]
Output: [[1]]
Example 3:
Input: root = []
Output: []
Constraints
 The number of nodes in the tree is in the range [0, 2000].
 1000 <= Node.val <= 1000
For diagrams refer to the 107 Binary Tree Level Order Traversal II notes.
Thinking Process
Define the Terms
Binary Tree : Binary means two. Tree with 0,1,2 children Level Order: Level means the height of the tree. Traversal: Visit all the nodes once
Define the Interface
Input: reference to root object Output: Array of arrays integers (node values)
Analyze the Input and Output
 For every level, the node values go into its own array.
 Can you identify the relationship between the input and the output?
 The indices in the output correspond the levels of the given input binary tree.
Identify the Invariants
 What is NOT changing in this problem?
 We cannot modify the binary tree.
 What rule does the output obey?
 Every node values corresponds to its level. You can see the relationship between the indices in the output array and nodes at a given level.
 What are the likely bugs that can happen?
 How can you prevent those bugs in your code?
 You cannot have null values in the output.
 Traverse left to right, top to bottom.
[3], [9,20], [15, 7]
Identify the constraints
 The number of nodes in the tree is in the range [0, 2000].
 1000 <= Node.val <= 1000
We have to handle the case when we have 0 nodes in the tree.
Classify the Problem
Tree Traversal
Analyze the Examples
 Empty tree (tree with no nodes), return empty array (ex3)
 Tree with one node, return the root node val in an array (ex2)
 Example 1 is non trivial case
Recursive Approach
Base Case
You can look at the constraint and check the lower bound for the number of nodes. This is the smallest instance of the problem. Example 3 is the base case.
Unit of Work
Look at example 3 to identify the unit of work.
 Traverse a level
 Grab the values of node
Binary Tree directly maps to the Recursion Tree. Do we need to do the work before or after the recursive call? At the root level, the problem is simpler, because you only have one node.
[3] needs to put in the output
We need to maintain the invariant that we grab all the nodes at the same level.
Problem Decomposition
 We have two subproblems.
 Unit of decomposition is one, cut off the root node.
 The left subtree is a tree
 The right subtree is a tree
 We will have two recursive calls in the code.
Keeping Track of State
Consider the root node, what is the state we need to keep track of?
 node.val, level (parent knows the level)
 We have identified the state for every node.
 We will have them as parameters to the recursive calls. It could be:
 variable in the class
 as a parameter to the method
Keeping Track of Tree Levels
How do we know the right subtree node level when we are on the left subtree? We leverage the level value and its relationship with the index in the output array. Since the number of node values in the array can vary 1, 2, 4, …
 How do you decide when we need to create a new array?
 How to avoid mixing up levels?
 The parent will create an empty array and provide the level for its child.
Parent Child Contract in Recursion Tree
The contract between the parent and child is that the parents will be responsible for creating the array for the children. Parent will also tell its children the level in which they are in the tree.
Analyze Time and Space Complexity
Time: O(N) Space: O(N)
Key Takeaways
[], level
[]
[[]]
output size, level
0, 0 1, 1
Implementation


For BFS what data structure will maintain the invariant? We need a queue.
Wrong Solution


Working Code (Iteration Approach)


Recursive Approach




Key Takeaways
 You can use the level as the index of the output where the array will contain the node values.
 Failed to identify the relationship of the location of the node values in the array and with the level value.
 We don’t need the index when we loop inside the while loop, we don’t have to use for loop with an index.
 How do we get all nodes for a given level in a recursive approach? The key is identify the state we need to keep track of for every node.
 The state we need for every node consists of the node value and the level.
 The way we keep all nodes at the same level in the output is by checking the length of the output with the level value. If they are the same, we create a new array for holding all elements at that level.
 We need to pass the level as a parameter to every recursive call.
Level order traversal is a common way to traverse a binary tree from left to right, level by level. We can achieve this using a queue data structure. Here’s how you can implement this:
 Initialize a Queue: Use a queue to store nodes at the current level.
 Use a Loop: Loop through the tree as long as there are nodes to process in the queue.
 Process Current Level: For the current level, store the values of nodes in a temporary list, and add the left and right children to the queue for the next level.
 Move to Next Level: Continue the loop until the queue is empty. The loop processes one level of the tree at a time.
Here’s the code:


This code will return a list of lists, where each inner list contains the values of nodes at a specific level of the tree, read from left to right.
The time complexity of this code is (O(n)), where (n) is the number of nodes in the tree, and the space complexity is (O(w)), where (w) is the maximum width of the tree (i.e., the maximum number of nodes at any level).
Define the Terms Binary Tree : Binary means two. Tree with 0,1,2 children Level Order: Level means the height of the tree. Traversal: Visit all the nodes once
Define the Interface Input: reference to root object Output: Array of arrays integers (node values)
Analyze the Input and Output For every level, the node values go into its own array. Can you identify the relationship between the input and the output? The indices in the output correspond the levels of the given input binary tree.
Identify the Invariants
 What is NOT changing in this problem?
 We cannot modify the binary tree
 What rule does the output obey?
 Every node values corresponds to its level You can see the relationship between the indices in the output array and nodes at a given level.
 What are the likely bugs that can happen? How can you prevent those bugs in your code?
 You cannot have null values in the output
 Traverse left to right, top to bottom [3], [9,20], [15, 7]
Identify the constraints
 The number of nodes in the tree is in the range [0, 2000].
 1000 <= Node.val <= 1000
We have to handle the case when we have 0 nodes in the tree.
Search the Problem Space
Classify the Problem Tree Traversal
Analyze the Examples
 Empty tree (tree with no nodes), return empty array (ex3)
 Tree with one node, return the root node val in an array (ex2)
 Example 1 is non trivial case
Solve the Problem by Hand
Describe the Pattern
Distill the Observations to Create Insights
Brute Force Approach
Recursive Approach
Base Case You can look at the constraint and check the lower bound for the number of nodes. This is smallest instance of the problem. Example 3 is the base case.
Unit of Work Look at example 3 to identify the unit of work.
Traverse a level Grab the values of node
Binary Tree directly maps to the Recursion Tree
Do we need to do the work before or after the recursive call?
At the root level, the problem is simpler, because
you only one node.
[3] needs to put in the output
We need to maintain the invariant that we grab all the
nodes at the same level.
We have two subproblems.
Unit of decomposition is cut off the root node.
The left subtree is a tree
The right subtree is a tree
We will have two recursive calls in the code.
Consider the root node, what is the state we
need to keep track of?
 node.val, level (parent knows the level)
We have identify the state for every node.
We will have them as parameters to the recursive calls
 variable in the class
 as a parameter
How do we know the right subtree nodes level when
we are on the left subtree?
We leverate the level value and its relationship with
the index in the output array.
Since the number of node values in the array can vary
1, 2, 4, ...
How do you decide when we need to create a new array?
How to avoid mixing up levels?
The parent will create an empty array and provides
the level for its child.
Contract between the parent and child
Parent will be responsible for creating the array
for the children.
Parent will also tell its children the level in
which they are in the tree.
Analyze Time and Space Complexity
Time: O( ) Space: O( )
Outline the Solution
Key Takeaways
[], level
[]
[[]]
output size, level 0, 0 1, 1
T: O(N) S: O(N)


For BFS what data structure will maintain the invariant? We need a queue


Define the Terms Binary Tree : Binary means two. Tree with 0,1,2 children Level Order: Level means the height of the tree. Traversal: Visit all the nodes once
Define the Interface Input: reference to root object Output: Array of arrays integers (node values)
Analyze the Input and Output For every level, the node values go into its own array. Can you identify the relationship between the input and the output? The indices in the output correspond the levels of the given input binary tree.
Identify the Invariants
 What is NOT changing in this problem?
 We cannot modify the binary tree
 What rule does the output obey?
 Every node values corresponds to its level You can see the relationship between the indices in the output array and nodes at a given level.
 What are the likely bugs that can happen? How can you prevent those bugs in your code?
 You cannot have null values in the output
 Traverse left to right, top to bottom [3], [9,20], [15, 7]
Identify the constraints
 The number of nodes in the tree is in the range [0, 2000].
 1000 <= Node.val <= 1000
We have to handle the case when we have 0 nodes in the tree.
Search the Problem Space
Classify the Problem Tree Traversal
Analyze the Examples
 Empty tree (tree with no nodes), return empty array (ex3)
 Tree with one node, return the root node val in an array (ex2)
 Example 1 is non trivial case
Solve the Problem by Hand
Describe the Pattern
Distill the Observations to Create Insights
Brute Force Approach
Recursive Approach
Base Case You can look at the constraint and check the lower bound for the number of nodes. This is smallest instance of the problem. Example 3 is the base case.
Unit of Work Look at example 3 to identify the unit of work.
Traverse a level Grab the values of node
Binary Tree directly maps to the Recursion Tree
Do we need to do the work before or after the recursive call?
At the root level, the problem is simpler, because
you only one node.
[3] needs to put in the output
We need to maintain the invariant that we grab all the
nodes at the same level.
We have two subproblems.
Unit of decomposition is cut off the root node.
The left subtree is a tree
The right subtree is a tree
We will have two recursive calls in the code.
Consider the root node, what is the state we
need to keep track of?
 node.val, level (parent knows the level)
We have identify the state for every node.
We will have them as parameters to the recursive calls
 variable in the class
 as a parameter
How do we know the right subtree nodes level when
we are on the left subtree?
We leverate the level value and its relationship with
the index in the output array.
Since the number of node values in the array can vary
1, 2, 4, ...
How do you decide when we need to create a new array?
How to avoid mixing up levels?
The parent will create an empty array and provides
the level for its child.
Contract between the parent and child
Parent will be responsible for creating the array
for the children.
Parent will also tell its children the level in
which they are in the tree.
Analyze Time and Space Complexity
Time: O( ) Space: O( )
Outline the Solution
Key Takeaways
[], level
[]
[[]]
output size, level 0, 0 1, 1


Identifying Problem Isomorphism
“Binary Tree Level Order Traversal” requires you to traverse a binary tree level by level, and return the values of nodes at each level in a separate list.
An isomorphic problem to this is “429. Nary Tree Level Order Traversal”. This problem also requires level order traversal, but the structure is an Nary tree instead of a binary tree. The traversal logic is quite similar  you would use a queue to perform a breadthfirst traversal. The only difference is that a node in an Nary tree can have more than two children, but this doesn’t significantly affect the overall approach.
“Nary Tree Level Order Traversal” is more complex due to the possibility of each node having more than two children. However, the traversal logic for both problems is essentially the same.
“Binary Tree Level Order Traversal” is a problem that tests your understanding of tree traversal using BreadthFirst Search (BFS). Here are 10 LeetCode problems that will help you prepare for it:
104. Maximum Depth of Binary Tree: This problem helps you understand the concept of depth in a tree.
101. Symmetric Tree: This problem helps you understand the concept of tree symmetry, which indirectly helps with traversal.
100. Same Tree: This problem will help you understand tree traversal to check if two trees are the same.
110. Balanced Binary Tree: This problem tests your understanding of the balance of a tree.
112. Path Sum: This problem involves traversal to find a path that sums up to a target.
111. Minimum Depth of Binary Tree: This problem will help you understand how to traverse a tree to find the minimum depth.
107. Binary Tree Level Order Traversal II: A variation of the level order traversal problem, but requires reversing the order, which could help with understanding tree traversals.
429. Nary Tree Level Order Traversal: This problem is a good practice to extend your understanding of level order traversal beyond binary trees.
226. Invert Binary Tree: This problem involves a manipulation of a binary tree structure and could help with understanding of tree traversal.
257. Binary Tree Paths: This problem requires knowledge of depthfirst search but can help with understanding path traversal in trees.
These cover tree traversal techniques and manipulation of binary tree structures, which are essential for the Level Order Traversal problem.








Problem Classification
This problem can be classified as follows:
Tree Traversal: This problem deals with visiting each node of a binary tree in a specific order, which is a form of tree traversal.
Binary Trees: The problem operates specifically on binary trees. Binary trees are a foundational concept in computer science and many problems are based on operations or manipulations related to them.
Graph Theory: While it’s more specialized, the binary tree is a type of graph. So this problem can also be seen as a part of graph theory.
Data Structure Manipulation: As you’re manipulating and accessing data within a specific data structure (a binary tree), this problem falls under the category of data structure manipulation.
Ordering and Sequencing: The problem involves a specific sequence in which nodes are to be visited and returned (from left to right, level by level). Therefore, it involves the concepts of ordering and sequencing.
These classifications help to categorize the problem and can give insights into potential strategies or concepts that could be useful in finding a solution.
Clarification Questions
What are the clarification questions we can ask about this problem?
Language Agnostic Coding Drills
Breaking down the code into smallest units of learning:
Understanding Basic Tree Traversal: The first concept to understand is basic tree traversal. In this code, a breadthfirst search (BFS) is used, which traverses the tree level by level from left to right. It starts from the root of the tree (or any arbitrary node of a graph) and explores the neighbor nodes at the current depth prior to moving on to nodes at the next depth level.
Queue Data Structure: A key component of BFS is the use of a queue data structure. A queue follows the FirstInFirstOut (FIFO) rule  the data that comes in first will be accessed first. A realworld example of a queue can be a singlelane oneway road, where the vehicle that enters first, leaves first. More than one vehicle can be in the queue at the same time. In Python, we can use the
deque
library for implementing a queue.2D List (Matrix) Handling: In Python, a matrix can be represented using a nested list where each row is a sublist. In this code,
levels
is a list of lists where each sublist represents a level in the tree.Null Checks and Optional Values: It’s essential to check for null values in tree nodes to avoid runtime errors. In Python, we can use the keyword
Optional
in the function definition to signify that the function argument may be None.Deque Operations: Deque operations are used extensively in this solution  for example,
append
(to add elements to the end),popleft
(to remove an element from the front), etc. It’s important to understand these operations to implement the solution.
The problem solving approach:
Initialize an empty queue and add the root node of the tree to it.
Initialize an empty 2D list. The 2D list will store the value of nodes at each level. The first level (root level) is added initially.
While there are still nodes in the queue, pop a node from the front of the queue.
For the popped node, check its left and right children. If they exist, add them to a temporary queue.
When the original queue is empty, this means we have finished one level of the tree. At this point, add the node values of all nodes in the temporary queue to the 2D list. Then, assign the temporary queue to the original queue and create a new temporary queue.
Repeat the process until the queue is empty, which means we have traversed all levels of the tree.
Return the 2D list, which contains the values of nodes at all levels.
Targeted Drills in Python
Drill 1: Basic Tree Traversal


Drill 2: Using Deque for Queue


Drill 3: Using 2D Lists


Drill 4: Null Checks and Optional Values


Drill 5: Deque Operations


Final Drill: Combining all concepts

