Level Order Traversal of Binary Tree

Try to solve the Level Order Traversal of Binary Tree problem.

We'll cover the following

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 00, then return “None” as the output.

Constraints:

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

  • −103≤-10^3 \leq Node.data ≤103\leq 10^3

Examples#

Created with Fabric.js 3.6.6 Output 100 50 200 25 75 350 Sample example 1 Input 100 : 50, 200 : 25, 75, 350 Same-level nodes, i.e., 50 and 200, areseparated by a comma.

1 of 3

Created with Fabric.js 3.6.6 Output 150 32 200 12 172 250 Input Sample example 2 150 : 32, 200 : 12, 172, 250 Same-level nodes, i.e., 12, 172 and 250, are separated by a comma.

2 of 3

Created with Fabric.js 3.6.6 Output Input Sample example 3 30 10 40 8 50 Same-level nodes, i.e., 8 and 50, are separated by a comma. 30 : 10, 40 : 8, 50

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

1

How does BFS ensure that it visits all nodes in a binary tree while traversing level by level?

A)

By using a stack data structure to keep track of visited nodes

B)

By using a queue data structure to maintain the order of node exploration

C)

By recursively traversing the left and right subtrees in a depth-first manner

D)

By randomizing the order of node exploration for better coverage

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Declare two queues, current_queue and next_queue.

Push the root node to current_queue and set the level to zero.

Dequeue the first element from current_queue and push its children in next_queue.

If current_queue is empty, increase the level number and swap the two queues.

Repeat until current_queue is empty.

Try it yourself#

Implement your solution in main.py in the following coding playground.

Note: The binary tree node’s class has members left and right to store references to other nodes, along with the member data to hold the node’s value.

Python
usercode > main.py
Input #1
%0 node_1 100 node_2 50 node_1->node_2 node_3 200 node_1->node_3 node_4 25 node_2->node_4 node_5 75 node_2->node_5 node_8 350 node_4->node_8 node_9 15 node_4->node_9 node_6 300 node_3->node_6 node_7 10 node_3->node_7
Visualization for Input #1
Level Order Traversal of a Binary Tree

Tree Breadth-first Search: Introduction

Solution: Level Order Traversal of Binary Tree