Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space.
For example:
1
\
2
\
5
/ \
3 6
\
4
For the above tree, the level order traversal is
1- > 2- > 5- > 3- > 6- > 4.
Input Format
You are given a function,
void levelOrder(Node * root) {
}
Constraints
1 <= Nodes in the tree <= 500
Output Format
Print the values in a single line separated by a space.
Sample Input
1
\
2
\
5
/ \
3 6
\
4
Sample Output
1 2 5 3 6 4
Explanation
Level Order Traversal: 1- > 2- > 5- > 3- > 6- > 4.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
struct node {
int data;
struct node *left;
struct node *right;
};
struct node* insert( struct node* root, int data ) {
if(root == NULL) {
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
} else {
struct 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;
}
}
/* you only have to complete the function given below.
node is defined as
struct node {
int data;
struct node *left;
struct node *right;
};
*/
void levelOrder( struct node *root) {
struct node *queue[500];
int queue_head, queue_end;
struct node *head;
if (!root)
return;
queue[0] = root;
queue_head = 0;
queue_end = 1;
while (queue_head < queue_end)
{
head = queue[queue_head++];
fprintf(stdout, "%d ", head->data);
if (head->left)
queue[queue_end++] = head->left;
if (head->right)
queue[queue_end++] = head->right;
}
}
int main() {
struct node* root = NULL;
int t;
int 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 <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node *left;
Node *right;
Node(int d) {
data = d;
left = NULL;
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;
}
}
/*
class Node {
public:
int data;
Node *left;
Node *right;
Node(int d) {
data = d;
left = NULL;
right = NULL;
}
};
*/
void levelOrder(Node * root) {
queue < Node*> q;
q.push(root);
while (!q.empty())
{
Node* root = q.front();
q.pop();
cout << root->data << ' ';
if (root->left) q.push(root->left);
if (root->right) q.push(root->right);
}
}
}; //End of Solution
int main() {
Solution myTree;
Node* root = NULL;
int t;
int data;
std::cin >> t;
while(t-- > 0) {
std::cin >> data;
root = myTree.insert(root, data);
}
myTree.levelOrder(root);
return 0;
}
#3 Code Example with Java Programming
Code -
Java Programming
import java.util.*;
import java.io.*;
class Node {
Node left;
Node right;
int data;
Node(int data) {
this.data = data;
left = null;
right = null;
}
}
class Solution {
/*
class Node
int data;
Node left;
Node right;
*/
public static void levelOrder(Node root)
{
LinkedList < Node> nodes = new LinkedList();
nodes.add(root);
while(!nodes.isEmpty())
{
if(nodes.peek().left != null)
nodes.add(nodes.peek().left);
if(nodes.peek().right != null)
nodes.add(nodes.peek().right);
System.out.print(nodes.poll().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 scan = new Scanner(System.in);
int t = scan.nextInt(>;
Node root = null;
while(t-- > 0) {
int data = scan.nextInt();
root = insert(root, data);
}
scan.close();
levelOrder(root);
}
}
#4 Code Example with Python Programming
Code -
Python Programming
class Node:
def __init__(self, info):
self.info = info
self.left = None
self.right = None
self.level = None
def __str__(self):
return str(self.info)
class BinarySearchTree:
def __init__(self):
self.root = None
def create(self, val):
if self.root == None:
self.root = Node(val)
else:
current = self.root
while True:
if val < current.info:
if current.left:
current = current.left
else:
current.left = Node(val)
break
elif val > current.info:
if current.right:
current = current.right
else:
current.right = Node(val)
break
else:
break
"""
Node is defined as
self.left (the left child of the node)
self.right (the right child of the node)
self.info (the value of the node)
"""
from collections import deque
def levelOrder(root):
#Write your code here
if not root: return
queue = deque()
queue.append(root)
while queue:
el = queue.popleft()
print(el.info, end = ' ')
if el.left:
queue.append(el.left)
if el.right:
queue.append(el.right)
tree = BinarySearchTree()
t = int(input())
arr = list(map(int, input().split()))
for i in range(t):
tree.create(arr[i])
levelOrder(tree.root)