Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/* Binary tree - Level Order Traversal */
#include<iostream>
#include<queue>
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<Node*> 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<<current->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
Copy link

locdoremon commented Mar 28, 2014

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

@mycodeschool
Copy link
Author

mycodeschool commented Apr 25, 2014

@locdoremon Its already there. :)

@chai2champ
Copy link

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
Copy link

rajmiglani commented Oct 31, 2014

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

@kaustubhkulkarni05
Copy link

kaustubhkulkarni05 commented Jan 29, 2015

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

@MayankPratap
Copy link

MayankPratap commented Sep 14, 2015

Your videos helped me learn a lot of topics -linked list,stack,queues,trees....
If I have to learn a DS/Algo topic,instead of going through a book....I first look at your videos....

@skmohit05
Copy link

skmohit05 commented Jul 20, 2016

code in C:

include <stdio.h>

include <stdlib.h>

include <string.h>

include <math.h>

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;

}

@yash9499
Copy link

yash9499 commented Oct 5, 2016

include<stdio.h>

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;
}

@yash9499
Copy link

yash9499 commented Oct 5, 2016

please help me find error

@aditya81070
Copy link

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?

@NishithaDundigala
Copy link

NishithaDundigala commented Dec 13, 2017

can you please upload java implementation of the binary tree using doubly linked list

@GunjanPardal
Copy link

GunjanPardal commented Oct 10, 2018

Java implementation of Level order traversal
bfs

import java.util.LinkedList;
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<>();
	queue.add(root);
	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) {
				queue.add(x.left);
			}
			if (x.right != null) {
				queue.add(x.right);
			}
		}
		// 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
Copy link

unique-versal commented Oct 22, 2018

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

@N01Z3B0t
Copy link

N01Z3B0t commented Mar 11, 2019

Saw your youtube lesson. Thank you. Better than my instructor.

@swapnil1505
Copy link

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
Copy link

Aditya-Ojha commented Jul 22, 2020

### 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
Copy link

uvedkhan commented Sep 13, 2020

Best Data Structure implementation so far

@ravi8190
Copy link

ravi8190 commented Sep 30, 2020

how to manage this code for user inputs

@hominini
Copy link

hominini commented Feb 15, 2021

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

@Bhabesh22
Copy link

Bhabesh22 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.

@Bhabesh22
Copy link

Bhabesh22 commented Jun 5, 2021

                      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

next whatever i am trying its going wrong. please help me out here.

@OtmanDaoudi
Copy link

OtmanDaoudi commented Jun 15, 2021

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;
}
}

void BreadthFirstTraversal(treeNode * root)
{
if(root == NULL) return;
else
{
Q * queue = NULL;
queue = enqueue(queue,root);
//printf("Queue head : %d ",queue->front->data->data);
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; 

}

@shahjigar556
Copy link

shahjigar556 commented Jun 19, 2021

very helpful

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment