Algorithm
Problem Name: 30 days of code -
Objective
Today, we're going further with Binary Search Trees. Check out the Tutorial tab for learning materials and an instructional video!
Task
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
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;
}
#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;
}
#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;
int T=Int32.Parse(Console.ReadLine()>;
while(T-->0){
int data=Int32.Parse(Console.ReadLine());
root=insert(root,data);
}
levelOrder(root);
}
}
#4 Code Example with Java Programming
Code -
Java Programming
import java.util.LinkedList;
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<>();
queue.add(root);
while (!queue.isEmpty()) {
Node curr = queue.remove();
System.out.print(curr.data + " ");
if (curr.left != null) queue.add(curr.left);
if (curr.right != null) queue.add(curr.right);
}
}
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);
}
}
#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) {
// Add your code here
// 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);
}>;
#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):
#Write your code here
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)
#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){
//Write your code here
$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);
?>