## Algorithm

Problem Name: 30 days of code - Day 23: BST Level-Order Traversal

Objective
Today, we're going further with Binary Search Trees. Check out the Tutorial tab for learning materials and an instructional video!

A level-order traversal, also known as a breadth-first search, visits each level of a tree's nodes from left to right, top to bottom. You are given a pointer, root , pointing to the root of a binary search tree. Complete the levelOrder function provided in your editor so that it prints the level-order traversal of the binary search tree.

Function Description

Complete the levelOrder function in the editor below.

levelOrder has the following parameter:
- Node pointer root: a reference to the root of the tree

Prints
- Print node.data items as space-separated line of integers. No return value is expected.

Input Format

The locked stub code in your editor reads the following inputs and assembles them into a BST:
The first line contains an integer, T (the number of test cases).
The T subsequent lines each contain an integer, data, denoting the value of an element that must be added to the BST.

Constraints

1 <= N <= 20

1 <= node.data[i] <= 100

Output Format

Print the data value of each node in the tree's level-order traversal as a single line of N space-separated integers.

Sample Input

``````6
3
5
4
7
2
1
``````

Sample Output

``````3 2 5 1 4 7
``````

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct Node{
struct Node* left;
struct Node* right;
int data;
}Node;
Node* newNode(int data){
Node* node=(Node*)malloc(sizeof(Node));
node->left=node->right=NULL;
node->data=data;
return node;
}

#define maxlvl(a,b) ((a>b )? a:b)
int mlvl =0;
void lvlp (Node* root,int lvl,int i)
{

if (i==(lvl) && root != NULL)
{
printf("%d ",root->data);}
else if (root != NULL) {
lvlp(root->left,lvl,i+1);
lvlp(root->right,lvl,i+1);
}
}

void treeH (Node* root,int i){
mlvl=   maxlvl(mlvl, i);

if (root != NULL) {
treeH(root->left,i+1);
treeH(root->right,i+1);
}

}
void levelOrder(Node* root){
treeH(root,0);
for (int i = 0 ;i  < = mlvl ;i++)
{
lvlp(root,i,0);
}

}

Node* insert(Node* root,int data){
if(root==NULL)
return newNode(data);
else{
Node* cur;
if(data < =root->data){
cur=insert(root->left,data);
root->left=cur;
}
else{
cur=insert(root->right,data);
root->right=cur;
}

}
return root;
}
int main(){
Node* root=NULL;
int T,data;
scanf("%d",&T);
while(T-->0){
scanf("%d",&data);
root=insert(root,data);
}
levelOrder(root);
return 0;

}
``````
Copy The Code &

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <cmath>
#include <iostream>
#include <queue>

using namespace std;

class Node {
public:
int data;
Node *left, *right;

Node(int d) {
data = d;
left = right = NULL;
}
};

class Solution {
public:
Node *insert(Node *root, int data) {
if (root == NULL) {
return new Node(data);
} else {
Node *cur;
if (data  < = root->data) {
cur = insert(root->left, data);
root->left = cur;
} else {
cur = insert(root->right, data);
root->right = cur;
}
return root;
}
}

void levelOrder(Node *root) {
queue < Node *> q;
q.push(root);

while (q.size() != 0) {
Node *curr = q.front();
q.pop();

cout << curr->data << " ";

if (curr->left) q.push(curr->left);
if (curr->right) q.push(curr->right);
}
}
};

int main() {
Solution myTree;
Node *root = NULL;
int T, data;
cin >> T;
while (T-- > 0) {
cin >> data;
root = myTree.insert(root, data);
}
myTree.levelOrder(root);
return 0;
}
``````
Copy The Code &

### #3 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Node{
public Node left,right;
public int data;
public Node(int data){
this.data=data;
left=right=null;
}
}
class Solution{

static void levelOrder(Node root)
{
var queue = new Queue < Node>();
queue.Enqueue(root);

while (queue.Count != 0)
{
Node curr = queue.Dequeue();
Console.Write(curr.data + " ");

if (curr.left != null) queue.Enqueue(curr.left);
if (curr.right != null) queue.Enqueue(curr.right);
}
}

static Node insert(Node root, int data){
if(root==null){
return new Node(data);
}
else{
Node cur;
if(data<=root.data){
cur=insert(root.left,data);
root.left=cur;
}
else{
cur=insert(root.right,data);
root.right=cur;
}
return root;
}
}
static void Main(String[] args){
Node root=null;
while(T-->0){
root=insert(root,data);
}
levelOrder(root);

}
}
``````
Copy The Code &

### #4 Code Example with Java Programming

```Code - Java Programming```

``````
import java.util.Queue;
import java.util.Scanner;

class Node {
Node left, right;
int data;

Node(int data) {
this.data = data;
left = right = null;
}
}

class Solution {
public static void levelOrder(Node root) {
Queue < Node> queue = new LinkedList<>();

while (!queue.isEmpty()) {
Node curr = queue.remove();
System.out.print(curr.data + " ");

}
}

public static Node insert(Node root, int data) {
if (root == null) {
return new Node(data);
} else {
Node cur;
if (data  < = root.data) {
cur = insert(root.left, data);
root.left = cur;
} else {
cur = insert(root.right, data);
root.right = cur;
}
return root;
}
}

public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
Node root = null;
while (T-- > 0) {
int data = sc.nextInt();
root = insert(root, data);
}
levelOrder(root);
}
}
``````
Copy The Code &

### #5 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
// Start of function Node
function Node(data) {
this.data = data;
this.left = null;
this.right = null;
}; // End of function Node

// Start of function BinarySearchTree
function BinarySearchTree() {
this.insert = function(root, data) {
if (root === null) {
this.root = new Node(data);

return this.root;
}

if (data  < = root.data) {
if (root.left) {
this.insert(root.left, data);
} else {
root.left = new Node(data);
}
} else {
if (root.right) {
this.insert(root.right, data);
} else {
root.right = new Node(data);
}
}

return this.root;
};

// Start of function levelOrder
this.levelOrder = function(root) {

// To print values separated by spaces use process.stdout.write(someValue + ' ')
var queue = [root];
while (queue.length > 0) {
var node = queue.shift();
write(node.data + " ");
if(node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
function write(str){
process.stdout.write(str);
}

}; // End of function levelOrder
}; // End of function BinarySearchTree

process.stdin.resume();
process.stdin.setEncoding('ascii');

var _input = "";

process.stdin.on('data', function (data) {
_input += data;
});

process.stdin.on('end', function () {
var tree = new BinarySearchTree();
var root = null;

var values = _input.split('\n').map(Number);

for (var i = 1; i < values.length; i++) {
root = tree.insert(root, values[i]);
}

tree.levelOrder(root);
}>;
``````
Copy The Code &

### #6 Code Example with Python Programming

```Code - Python Programming```

``````
import sys

class Node:
def __init__(self,data):
self.right=self.left=None
self.data = data
class Solution:
def insert(self,root,data):
if root==None:
return Node(data)
else:
if data<=root.data:
cur=self.insert(root.left,data)
root.left=cur
else:
cur=self.insert(root.right,data)
root.right=cur
return root

def levelOrder(self,root):
queue = [root]
while len(queue) is not 0:
curr = queue[0]
queue = queue[1:]
print(str(curr.data) + " ", end="")

if curr.left is not None:
queue.append(curr.left)
if curr.right is not None:
queue.append(curr.right)

T=int(input())
myTree=Solution()
root=None
for i in range(T):
data=int(input())
root=myTree.insert(root,data)
myTree.levelOrder(root)
``````
Copy The Code &

### #7 Code Example with PHP Programming

```Code - PHP Programming```

``````
left=\$this->right=null;
\$this->data = \$data;
}
}
class Solution{
public function insert(\$root,\$data){
if(\$root==null){
return new Node(\$data);
}
else{
if(\$data < =\$root->data){
\$cur=\$this->insert(\$root->left,\$data);
\$root->left=\$cur;
}
else{
\$cur=\$this->insert(\$root->right,\$data);
\$root->right=\$cur;
}
return \$root;
}
}

public function levelOrder(\$root){
\$data = [];
\$queue[] = \$root;

while (!empty(\$queue)) {
\$curr = array_shift(\$queue);
\$data[] = (int)\$curr->data;

if (\$curr->left !== null) {
\$queue[] = \$curr->left;
}
if (\$curr->right !== null) {
\$queue[] = \$curr->right;
}
}

echo implode(' ', \$data);
}

}//End of Solution
\$myTree=new Solution();
\$root=null;
\$T=intval(fgets(STDIN));
while(\$T-->0){
\$data=intval(fgets(STDIN));
\$root=\$myTree->insert(\$root,\$data);
}
\$myTree->levelOrder(\$root);
?>

``````
Copy The Code &