Solution: Level Order Traversal of Binary Tree

Statement#

Given the root of a binary tree, display the values of its nodes while performing a level order traversal. Return the node values for all levels in a string separated by the character :. If the tree is empty, i.e., the number of nodes is $0$, then return “None” as the output.

Constraints:

• The number of nodes in the tree is in the range $[0, 500]$.

• $-10^3 \leq$ Node.data $\leq 10^3$

Solution#

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach#

The naive approach would be to first calculate the height of the tree and then recursively traverse it, level by level. The printing function would be called for every level in the range $[1, height]$.

In the case of a skewed tree, the time complexity for this approach would be $O(n^2)$, where $n$ is the number of nodes. The space complexity is $O(n)$.

Optimized approach using tree breadth-first search#

We can traverse a binary tree using the depth or breadth-first search pattern. The fundamental characteristic of the depth-first search pattern is that it travels as far as possible along each tree branch before exploring the others.

However, since we are asked to print all nodes at the same hierarchical level, this problem naturally falls under the tree breadth-first search pattern. It starts searching at the root node and moves down level by level, exploring adjacent nodes at level $k + 1$. We’ll print all the nodes at each level and then move to the next level.

Solution 1#

We can conduct level order traversal of a binary tree using two queues, similar to breadth-first search. This technique efficiently explores the tree structure, showcasing the BFS method for systematic node processing at each level.

We can use two queues to solve this problem:

• A current queue
• A next queue

The slides below illustrate how we would like the algorithm to run:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction#

• First, we’ll declare an array of two queues. This step will help us swap values between our two queues later.

• We then declare and point current_queue to the $0^{th}$ index and next_queue to the $1^{st}$ index of the queues array.

• We’ll start by pushing the root node to current_queue and setting the tree level to zero.

We’ll carry out the following operations until current_queue is empty:

• Dequeue the first element of current_queue.

• Enqueue its children to next_queue.

• Store the dequeued node in result.

• The loop in the code above runs once, since we only have one node in current_queue. To ensure all the tree nodes are visited, we’ll swap current_queue and next_queue once the former becomes empty.

• We’ll swap current_queue with next_queue and increment level_number by $1$. Since we’re moving to the next level, we’ll also append : to result.

• We terminate the loop if current_queue is still empty and return the result.

Just the code#

Here’s the complete solution to this problem:

Solution summary#

To recap, the solution to this problem can be divided into the following parts:

1. Use two queues, current_queue and next_queue, to keep track of the nodes.

2. Dequeue nodes from current_queue and push their children to the next_queue.

3. Store the dequeued nodes in result.

4. If the former queue is empty in step 3, swap the two queues and increment the level number.

5. Return result once the loop terminates.

Time complexity#

The time complexity of this solution is linear, $O(n)$, where $n$ is the number of nodes, because every node is visited and printed only once.

Space complexity#

The space complexity of this solution is linear, $O(n)$, since the algorithm instantiates queues that take up space of up to $\lceil{^n/_2}\rceil$ nodes. This is because the maximum queue size occurs at the level of the leaf nodes of a balanced binary tree.

Solution 2#

In the previous solution, we used two queues to keep track of the current level. However, there is an alternative approach to conduct level order traversal on a binary tree using a single deque. It efficiently traverses the tree by processing nodes at each level in a breadth-first manner. By iteratively dequeuing nodes and collecting their data values, it constructs a hierarchical representation of the tree.

The steps for this solution are as follows:

• Initialize an empty list called result. This list will hold the data of nodes visited in the level order.

• Check if the tree is empty. If so, we return the empty result list.

• Next, create a deque named current_queue to facilitate breath-first traversal.

• Start by enqueuing the root node to initiate the traversal process.

• Begin a loop that continues until current_queue is empty.

• Now, determine the number of nodes at the current level by getting the length of current_queue. Also, initialize an empty list, level_nodes, to store the data of nodes at this level.

• Next, iterate over the number of nodes in the current level:

  • Dequeue a node (temp) from the front of current_queue.
  • Append the string representation of the node’s data to level_nodes.
  • Enqueue the left and right child of the node(if any) we dequeued in the previous step into current_queue.

• After processing all nodes at current levels, join the elements in level_nodes into a single string with “,” as a separator.

• Append this string to the result list, representing one level of the traversal.

• Once the traversal is complete, join all the level representations stored in the result list into a single string with " : " as the separator.

• Print the resultant, the string which represents the level-order traversal of the binary tree.

Here’s an example to demonstrate the algorithm mentioned above:

Solution summary#

To recap, the solution to this problem can be divided into the following steps:

1. Start by initializing an empty result list and a queue, pushing the root onto the queue.
2. While the queue is not empty, iterate over each level, dequeuing nodes one by one and enqueuing their children.
3. Collect the data of nodes at each level, join them into strings, and append them to the result list.
4. Finally, join the level strings with " : " and return the resulting string representing the level-order traversal.

Time complexity#

The time complexity of this solution is linear, $O(n)$, where $n$ is the number of nodes, because every node is visited and printed only once.

Space complexity#

The space complexity of this solution is linear, $O(n)$, since the algorithm instantiates queues that take up space of up to $\lceil{^n/_2}\rceil$ nodes. This is because the maximum queue size occurs at the level of the leaf nodes of a balanced binary tree.