Coderust: Hacking the Coding Interview/

...

/

Level Order Traversal of Binary Tree

Level Order Traversal of Binary Tree

Given the root of a binary tree, display its level-order traversal.

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. We must print node values for all levels separated by the specified character, :.

Example

Let’s look at the tree below as an example:

G root 100 node1 50 root->node1 node2 200 root->node2 node3 25 node1->node3 node4 75 node1->node4 node6 350 node2->node6

The level-order traversal for the above tree will look like this:

100 : 50, 200 : 25, 75, 350

Sample Input

The input list below represents the level-order traversal of the binary tree:

[100, 50, 200, 25, 75, 350]

Expected Output

The sequence below represents the level-order traversal of the binary tree we expect to print:

100 : 50, 200 : 25, 75, 350

Try it yourself

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.

main.cpp
BinaryTree.cpp
BinaryTreeNode.cpp
#include "BinaryTree.cpp"
#include <queue>
using namespace std;
void LevelOrderTraversal(BinaryTreeNode* root) {
	// TODO: Write - Your - Code
	cout << "";
}

Solution 1

We need two queues to solve this problem:

  • The current queue
  • The next queue

We will conform to the following steps for this solution:

  1. First, we declare an array of two queues. This step will help us, later on, to swap values between our two queues.

  2. We then declare and point the current queue to the 0th0^{th} ...