Instantly share code, notes, and snippets.

# mycodeschool/LevelOrder_CPP.cpp

Last active May 19, 2024 03:09
Show Gist options
• Save mycodeschool/9507131 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* Binary tree - Level Order Traversal */ #include #include using namespace std; struct Node { char data; Node *left; Node *right; }; // Function to print Nodes in a binary tree in Level order void LevelOrder(Node *root) { if(root == NULL) return; queue Q; Q.push(root); //while there is at least one discovered node while(!Q.empty()) { Node* current = Q.front(); Q.pop(); // removing the element at front cout<data<<" "; if(current->left != NULL) Q.push(current->left); if(current->right != NULL) Q.push(current->right); } } // Function to Insert Node in a Binary Search Tree Node* Insert(Node *root,char data) { if(root == NULL) { root = new Node(); root->data = data; root->left = root->right = NULL; } else if(data <= root->data) root->left = Insert(root->left,data); else root->right = Insert(root->right,data); return root; } int main() { /*Code To Test the logic Creating an example tree M / \ B Q / \ \ A C Z */ Node* root = NULL; root = Insert(root,'M'); root = Insert(root,'B'); root = Insert(root,'Q'); root = Insert(root,'Z'); root = Insert(root,'A'); root = Insert(root,'C'); //Print Nodes in Level Order. LevelOrder(root); }

### locdoremon commented Mar 28, 2014

I hope you soon release other binary tree traversal algorithms: Preoder,Inoder,Postoder

### chai2champ commented Jun 22, 2014

even though im from core electronics student i get quick review through ur teaching...may god bless u sir..ur kind of angel to software engineering students

### rajmiglani commented Oct 31, 2014

rightly said chai2champ..same with me.thankyou sir.

### kaustubhkulkarni05 commented Jan 29, 2015

Can you please upload java implementation for BFS and DFS (preorder , inorder , postorder)?

### MayankPratap commented Sep 14, 2015

If I have to learn a DS/Algo topic,instead of going through a book....I first look at your videos....

code in C:

# define MAX 10

struct BstNode{
int data;
struct BstNode* left;
struct BstNode* right;
};

BstNode* arr[MAX];
int front = -1, rear = -1;

bool isEmpty(){
return (front == -1 && rear == -1) ? true : false;
}

bool isFull(){
return (rear+1)%MAX == front ? true : false;
}

void enQueue(BstNode* x){
if(isFull()){
printf("queue is full\n");
return;
}
if(isEmpty())
front = rear = 0;
else
rear = (rear+1)%MAX;

``````arr[rear] = x;
``````

}
void deQueue(){
if(isEmpty()){
printf("queue is empty\n");
return;
}
else if(front == rear)
front = rear = -1;
else
front = (front+1)%MAX;

}

BstNode* getNewNode(int d){
BstNode* newNode = (BstNode*)malloc(sizeof(BstNode));
newNode->data = d;
newNode->left = newNode->right = NULL;

``````return newNode;
``````

}

BstNode* Insert(BstNode* root, int d){
BstNode* newNode = getNewNode(d);
if(root == NULL){
root = newNode;
}
else if(d <= root->data){
root->left = Insert(root->left, d);
}
else
root->right = Insert(root->right, d);

``````return root;
``````

}

void levelOrder(BstNode* root){
if(root == NULL) return;
enQueue(root);
while(!isEmpty()){
BstNode* current = arr[front];
deQueue();
printf("%d ", current->data);
if(current->left != NULL) enQueue(current->left);
if(current->right != NULL) enQueue(current->right);

``````}
``````

}

int main(){
BstNode* root = NULL;
root = Insert(root,5);
root = Insert(root,10);
root = Insert(root,15);
root = Insert(root,7);
root = Insert(root,3);
root = Insert(root,20);
root = Insert(root,25);
root = Insert(root,21);
levelOrder(root);

``````return 0;
``````

}

# include<malloc.h>

struct node{
int data;
struct node* left;
struct node*right;

};

struct node1* temp;
struct node1{
int top;
struct node *A[10];

};
struct node* create();
void preorder(struct node* root);
struct node* create(){
int x;
struct node* p=(struct node_)malloc(sizeof(struct node));
scanf("%d",&x);
if(x==-1)
return NULL;
else
{ p->data=x;
p->left=create();
p->right=create();
}
return p;
}
void push(struct node_ root){
temp->top=temp->top+1;
temp->A[temp->top]=root;

}
void pop(){
//printf("%d",temp->A[temp->top]->data);
temp->top=temp->top-1;

}
void preorder(struct node* root){
temp=(struct node1_)malloc(sizeof(struct node1));
temp->top=-1;
if(root==NULL)
return;
push(root);
while((temp->top)!=-1)
{
struct node_ current=root;
printf("%d",current->data);
pop();

``````    if(current->left!=NULL)
push(current->left);

if(current->right!=NULL)
push(current->right);

}
``````

}
int main(void){
struct node* root;
root=create();
preorder(root);
return 0;
}

### aditya81070 commented Oct 29, 2017

Thank you sir for making DSA so easy to understand with these short and sweet videos.
I wanna to ask that is there any repository that I can clone for all source codes?

### GunjanPardal commented Oct 10, 2018

Java implementation of Level order traversal

import java.util.Queue;

public class BinaryTree {
private Node root;
private class Node {
int data;
Node left;
Node right;

``````	Node(int data) {
this.data = data;
}
}

public void insert(int data) {
root = insert(root, data);

}

private Node insert(Node x, int data) {
if (x == null) {
return new Node(data);
}
if (data < x.data) {
x.left = insert(x.left, data);
} else {
x.right = insert(x.right, data);
}
return x;

}

public void printLineByLine() {
printLineByLine(root);
}

private void printLineByLine(Node root) {
if (root == null) {
return;
}

final Queue<Node> queue = new LinkedList<>();
while (!queue.isEmpty()) {
final int size = queue.size();
for (int i = 0; i < size; i++) {
Node x = queue.remove();
System.out.print(x.data + " ");
if (x.left != null) {
}
if (x.right != null) {
}
}
// new level
System.out.println();
}
}
``````

}

import java.util.Random;

public class Main {

``````public static void main(String[] args) {
final Random random = new Random();
final int N = 6;
final int M = 100;
final BinaryTree tree = new BinaryTree();
for (int i = 0; i < N; i++) {
tree.insert(random.nextInt(M));
}
tree.printLineByLine();
}

}
``````

### unique-versal commented Oct 22, 2018

...............................................

### swapnil1505 commented Sep 27, 2019

how about binary tree traversal its not binary tree but binary search tree.left side of root node is lesser also right side is higher.

### Aditya-Ojha commented Jul 22, 2020 • edited

### CODE IN C

``````
#include <stdio.h>
#include <stdlib.h>
#define n 100

struct BstNode* queue[n];
int front=-1,rear=-1;

void Enqueue();
void Dequeue();
struct BstNode* first();
int isEmpty();
struct BstNode* insert();
struct BstNode* NewNode();
void LevelOrder();

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
struct BstNode{
int data;
struct BstNode* right;
struct BstNode* left;
};

void Enqueue(struct BstNode* x){
if(front==-1&&rear==-1){
front=rear=0;
}else if((rear+1)%n==front){
printf("Memory Full\n");exit(1);
}else{
rear = (rear+1)%n;
}
queue[rear] = x;
}
void Dequeue(){
if(front==-1&&rear==-1)return;
if(front==0&&rear==0){
front=rear=-1;
}else{
front = (front+1)%n;
}
}
struct BstNode* first(){
return queue[front];
}
int isEmpty(){
if(front==-1&&rear==-1) return 1;
return 0;
}

int main(){
struct BstNode* root = NULL;

root = insert(root,3);
root = insert(root,6);
root = insert(root,1);
root = insert(root,9);
root = insert(root,11);
root = insert(root,8);
root = insert(root,10);
root = insert(root,19);
root = insert(root,5);
LevelOrder(root);

return 0;
}
struct BstNode* insert(struct BstNode* root,int data){
if(root==NULL){
root = NewNode(data);
}else if(data<=root->data){
root->left = insert(root->left,data);
}else if(data>root->data){
root->right = insert(root->right,data);
}
return root;

}
struct BstNode* NewNode(int data){
struct BstNode* temp = (struct BstNode*)malloc(sizeof(struct BstNode));
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void LevelOrder(struct BstNode* root){
if(root==NULL) return;
Enqueue(root);
while(!isEmpty()){
struct BstNode* current = first();
printf("%d ",current->data);
if(current->left!=NULL) Enqueue(current->left);
if(current->right!=NULL) Enqueue(current->right);
Dequeue();
}
}
``````

### uvedkhan commented Sep 13, 2020

Best Data Structure implementation so far

### ravi8190 commented Sep 30, 2020

how to manage this code for user inputs

### byron-perez commented Feb 15, 2021

I just want to say thanks to you for sharing the resources.

### Bhabesh142 commented Jun 5, 2021

Started learning DS since last 25 days back, not sure about other programming language. I can modify DS in C/C++ program after learning it from the YouTube channel and the challenge it gives to write some codes of your own after declaring some functions how much it is required others we need to write. Thank you MyCodeSchool for helping me out to learn new techniques in DS.

### Bhabesh142 commented Jun 5, 2021 • edited

``````                      F
/   \
D      J
/ \    / \
B   E   G   K
/ \ / \ / \    \
A  CS LN I   T
/
H
``````

Hello All Can Anybody. Help me out with this Binary Tree-Level Order Traversal.?
I tried and reached till this much only:-
int main()
{
Node* root = NULL;
root = Insert(root,'F'); root = Insert(root,'D');
root = Insert(root,'J'); root = Insert(root,'K');
root = Insert(root,'B'); root = Insert(root,'E');
root = Insert(root,'G'); root = Insert(root,'S');
root = Insert(root,'A'); root = Insert(root,'C');
root = Insert(root,'L'); root = Insert(root,'N');
LevelOrder(root);
}
I get output as: - F D J B E G K A C S L N

Output I want as: - F D J B E G K A C S L N I T H

### OtmaneDaoudi commented Jun 15, 2021 • edited

Here is my version of it (note! : I implemented my own version of Queues and all its operations:
#include<stdio.h>
#include<stdlib.h>

struct treeNode
{
int data;
struct treeNode * left;
struct treeNode * right;
};
typedef struct treeNode treeNode ;

struct node
{
treeNode * data;
struct node * next;
};
typedef struct node node;

struct Q{
node * front;
node * rear;
};
typedef struct Q Q;

int isEmpty(Q * queue)
{
return (queue == NULL || queue->front == NULL);
}

Q * enqueue(Q * queue , treeNode * data)
{
if(isEmpty(queue))
{
queue = (Q *)malloc(sizeof(Q));
queue->front = (node *)malloc(sizeof(node));
queue->front->data = data;
queue->front->next = NULL;
queue->rear = queue->front;
return queue;
}
else if(data == NULL) return queue;
else
{
queue->rear->next = (node *)malloc(sizeof(node));
queue->rear->next->data = data;
queue->rear->next->next = NULL;
queue->rear = queue->rear->next;
return queue;
}
}

void dequeue(Q * queue)
{
if(isEmpty(queue)) return;
else
{
node * toFree = queue->front;
queue->front = queue->front->next;
free(toFree);
}
}

node * front( Q * queue)
{
if(isEmpty(queue)) return fprintf(stderr,"can't read from a NULL pointer");
else
{
return queue->front;
}
}

{
if(root == NULL) return;
else
{
Q * queue = NULL;
queue = enqueue(queue,root);
printf("\nQueue : ");
while(!isEmpty(queue))
{
node * frontElement = front(queue);
printf(" %d",frontElement->data->data);
queue = enqueue(queue,frontElement->data->left);
queue = enqueue(queue,frontElement->data->right);
dequeue(queue);
}
}
}

void insert(treeNode ** ptrToRoot , int data) //using recursion
{
if(*ptrToRoot == NULL)
{
*ptrToRoot = (treeNode *)malloc(sizeof(treeNode));
(*ptrToRoot)->data = data;
(*ptrToRoot)->left = NULL;
(*ptrToRoot)->right = NULL;
}
else if(data > (*ptrToRoot)->data)
{
insert(&(*ptrToRoot)->right,data);
}
else if(data <= (*ptrToRoot)->data)
{
insert(&(*ptrToRoot)->left,data);
}
}

int main()
{
treeNode *tree = NULL;
insert(&tree,1);
insert(&tree,100);
insert(&tree,-1);
insert(&tree,8);
insert(&tree,6);

``````BreadthFirstTraversal(tree);
return 0;
``````

}

### AnuragUmale commented Dec 30, 2022

void LevelOrder(struct BstNode* root){
if(root==NULL) return;

Very Hepful

# \$\$\large\textcolor{yellow}{\textsf{JavaScript} \space \color{white}\textsf{Version is here..!}}\$\$

```class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}

// Method to insert a node into the Binary Search Tree rooted at this node
insert(data) {
if (data <= this.data) {
this.left === null ? this.left = new Node(data) : this.left.insert(data);
} else {
this.right === null ? this.right = new Node(data) : this.right.insert(data);
}
}
}

/*
-> Level Order Traversal
*/

function levelOrder(root, queue = [], result = []) {
if (!root) return

queue.push(root)
while(queue.length) {
const currentNode = queue.shift();
result.push(currentNode.data)
if(currentNode.left) queue.push(currentNode.left)
if(currentNode.right) queue.push(currentNode.right)
}

return result;
}

/* Creating the root node
with example tree for testing

M
/ \
B   Q
/ \   \
A   C   Z
*/

const root = new Node('M');

// Insert nodes into the BST using the insert method
root.insert('B');
root.insert('Q');
root.insert('Z');
root.insert('A');
root.insert('C');

levelOrder(root))  // [ 'M', 'B', 'Q', 'A', 'C', 'Z' ]```

### amu-cell commented Nov 28, 2023

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct queue {
int data;
struct queue* next;

};
struct queue* front = NULL;
struct queue* rear = NULL;
void push(struct queuenode) {
struct queue
temp = (struct queue*)malloc(sizeof(struct queue));
temp->data = node->data;
temp->next = NULL;
if (rear == NULL && front == NULL) {
front = rear = temp;
return;
}rear->next = temp;
rear = temp;
}
void pop() {
struct queue* temp = front;
if (rear == NULL && front == NULL) {
return;
}if (front == rear) {
front = rear = NULL;
}
front = front->next;
free(temp);
}
struct BstNode {
int data;
struct BstNode* left;
struct BstNode* right;
};

struct BstNode* Getnewnode(int data) {
struct BstNode* newnode = (struct BstNode*)malloc(sizeof(struct BstNode));
newnode->data = data;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
struct BstNode* Insert(struct BstNode* root, int data) {
if (root == NULL) {
root = Getnewnode(data);
}
else if (data <= root->data) {
root->left = Insert(root->left, data);
}
else {
root->right = Insert(root->right, data);
}return root;
}

struct queue*get() {

`````` return  front;
``````

}
void Levelorder(struct BstNoderoot ) {
if (root == NULL) {
return;
}push(root);
while (front != NULL && rear != NULL) {
struct BstNode
current =get() ;

``````	printf("%d ", current->data);if (current->left != NULL)push(current->left);
if (current->right!= NULL)push(current->right);
pop();
}
``````

}
int main() {
struct BstNode* root = NULL;
root = Insert(root, 3);
root = Insert(root, 6);
root = Insert(root, 1);
root = Insert(root, 9);
root = Insert(root, 11);
root = Insert(root, 8);
root = Insert(root, 10);
root = Insert(root, 19);
root = Insert(root, 5);
Levelorder(root);
return 0;
}### 求助只能打印出来第一个root