Binary Tree Level Order Traversal

title: Binary Tree Level Order Traversal tags: level-order-tree-traversal 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def level_wrapper(node, level, output)
  # We need this to climb up the tree and handle the empty tree. We need to handle the leaves.
  if node.nil?
    return
  end
    
  if output.size == level
    output << []
  end

  # UoW
  output[level] << node.val
    
  level_wrapper(node.left, level+1, output)
  level_wrapper(node.right, level+1, output)
end

# @param {TreeNode} root
# @return {Integer[][]}
def level_order(root)
  output = []
  level = 0
  
  level_wrapper(root, level, output)
  output
end

def level_wrapper(node, level, output)
  # We need this to climb up the tree and handle the empty tree. We need to handle the leaves.
  if node.nil?
    return
  end
    
  if output.size == level
    output << []
  end

  # UoW
  output[level] << node.val
    
  level_wrapper(node.left, level+1, output)
  level_wrapper(node.right, level+1, output)
end

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

Wrong Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def level_order(root)
  output = []
  queue = [root]
    
  while !queue.empty?  
    size = queue.size
    nodes = []

    size.times do
      node = queue.shift
      nodes << node 
      queue << node.left if node.left
      queue << node.right if node.right
    end
    
    output << nodes
  end

  return output
end

Working Code (Iteration Approach)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Integer[][]}
def level_order(root)
  if root.nil?
    return []
  end
  
  output = []
  queue = [root]
  level = 0
    
  while !queue.empty?  
    level_size = queue.size
    output << []

    level_size.times do
      node = queue.shift
      output[level] << node.val
          
      queue << node.left if node.left
      queue << node.right if node.right
    end

    level += 1
  end

  return output
end

Recursive Approach

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end

def level_wrapper(node, level, output)
  # start a new level
  if output.size == level
    output << []
  end
  
  # Unit of Work
  output[level] << node.val
    
  if node.left
    level_wrapper(node.left, level + 1, output)
  end
  
  if node.right
    level_wrapper(node.right, level + 1, output)
  end
end

# @param {TreeNode} root
# @return {Integer[][]}
def level_order(root)
  if root.nil?
    return []
  end
  
  output = []
  level_wrapper(root, 0, output)
  output
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# @param {TreeNode} root
# @return {Integer[][]}
def level_order(root)
  output = []
  
  if root.nil?
    return output
  end
    
  queue = [root]
  
  while !queue.empty?
    # to maintain the invariant
    size = queue.size
    nodes = []
    # Implicitly maintains the invariant without using level variable
    size.times do
      # deque from the queue
      node = queue.shift 
      nodes << node.val
      queue << node.left if node.left
      queue << node.right if node.right
    end
    
    output << nodes
  end
    
  return output
end

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        result = []
        queue = deque([root])

        while queue:
            level_size = len(queue)
            current_level = []

            for _ in range(level_size):
                node = queue.popleft()
                current_level.append(node.val)

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            result.append(current_level)

        return result

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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def level_wrapper(node, level, output)
#     we need this to climb up the tree and handle the empty tree. We need to handle leaf.
    if node.nil?
        return
    end

    if output.size == level
        output << []
    end
#     UoW
    output[level] << node.val

    level_wrapper(node.left, level+1, output)
    level_wrapper(node.right, level+1, output)
end

# @param {TreeNode} root
# @return {Integer[][]}
def level_order(root)
    output = []
    level = 0
    level_wrapper(root, level, output)
    output
end

def level_wrapper(node, level, output)
#     we need this to climb up the tree and handle the empty tree. We need to handle leaf.
    if node.nil?
        return
    end

    if output.size == level
        output << []
    end
#     UoW
    output[level] << node.val

    level_wrapper(node.left, level+1, output)
    level_wrapper(node.right, level+1, output)
end

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end

# @param {TreeNode} root
# @return {Integer[][]}
def level_order(root)
  output = []
    if root.nil?
        return output
    end

  queue = [root]

  while !queue.empty?
#       to maintain the invariant
      size = queue.size
      nodes = []
      size.times do
#           deque from the queue
         node = queue.shift 
         nodes << node.val
         queue << node.left if node.left
         queue << node.right if node.right
      end
      output << nodes
  end

  return output
end

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)

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end

def level_wrapper(node, level, output)
#     we need this to climb up the tree and handle the empty tree. We need to handle leaf.
    if node.nil?
        return
    end

    if output.size == level
        output << []
    end
#     UoW
    output[level] << node.val

    level_wrapper(node.left, level+1, output)
    level_wrapper(node.right, level+1, output)
end

# @param {TreeNode} root
# @return {Integer[][]}
def level_order(root)
    output = []
    level = 0
    level_wrapper(root, level, output)
    output
end

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. N-ary Tree Level Order Traversal”. This problem also requires level order traversal, but the structure is an N-ary tree instead of a binary tree. The traversal logic is quite similar - you would use a queue to perform a breadth-first traversal. The only difference is that a node in an N-ary tree can have more than two children, but this doesn’t significantly affect the overall approach.

“N-ary 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 Breadth-First 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. N-ary 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 depth-first 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def level_order(root)
  output = []
  queue = [root]

  while !queue.empty?  
     size = queue.size
     nodes = []
      size.times do
         node = queue.shift
         nodes << node 
         queue << node.left if node.left
         queue << node.right if node.right
      end
      output << nodes
  end

    return output
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Integer[][]}
def level_order(root)
    if root.nil?
        return []
    end
  output = []
  queue = [root]
  level = 0

  while !queue.empty?  
     level_size = queue.size
     output << []
      level_size.times do
         node = queue.shift
         output[level] << node.val
          
         queue << node.left if node.left
         queue << node.right if node.right
      end
      level += 1
  end

    return output
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import deque
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        Q = deque([root])
        levels = [[root.val]]
        temp = deque()

        while Q:
            node = Q.popleft()
            if node.left: temp.append(node.left)
            if node.right: temp.append(node.right)
            
            if not Q:
                if temp:
                    levels.append([n.val for n in temp])
                Q = temp
                temp = deque()

        return levels

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end

def level_wrapper(node, level, output)
#     start a new level
    if output.size == level
        output << []
    end
#     Unit of Work
    output[level] << node.val

    if node.left
        level_wrapper(node.left, level + 1, output)
    end
    if node.right
        level_wrapper(node.right, level + 1, output)
    end
end

# @param {TreeNode} root
# @return {Integer[][]}
def level_order(root)
    if root.nil?
        return []
    end
    output = []
    level_wrapper(root, 0, output)
    output
end

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 breadth-first 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 First-In-First-Out (FIFO) rule - the data that comes in first will be accessed first. A real-world example of a queue can be a single-lane one-way 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Node:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def bfs(root):
    queue = [root]
    while queue:
        node = queue.pop(0)
        print(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
bfs(root)

Drill 2: Using Deque for Queue

1
2
3
4
5
6
from collections import deque

queue = deque([1,2,3])
queue.append(4)
print(queue.popleft())
print(queue)

Drill 3: Using 2D Lists

1
2
matrix = [[1,2,3],[4,5,6],[7,8,9]]
print(matrix[1][2]) 

Drill 4: Null Checks and Optional Values

1
2
3
4
5
6
7
8
def check_none(value):
    if value is None:
        return "None found!"
    else:
        return "Value exists!"

print(check_none(None))
print(check_none(5))

Drill 5: Deque Operations

1
2
3
4
5
6
from collections import deque

queue = deque([1,2,3])
queue.append(4)  
queue.popleft()  
print(queue)

Final Drill: Combining all concepts

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from collections import deque

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

class Solution:
    def levelOrder(self, root):
        if not root:
            return []
        queue = deque([root])
        levels = [[root.val]]
        temp = deque()

        while queue:
            node = queue.popleft()
            if node.left: temp.append(node.left)
            if node.right: temp.append(node.right)

            if not queue:
                if temp:
                    levels.append([n.val for n in temp])
                queue = temp
                temp = deque()

        return levels

root = Node(1)
root.left = Node(2)
root.right = Node(3)

solution = Solution()
print(solution.levelOrder(root))