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

This comment has been minimized.

Copy link

@locdoremon locdoremon commented Mar 28, 2014

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

@mycodeschool

This comment has been minimized.

Copy link
Owner Author

@mycodeschool mycodeschool commented Apr 25, 2014

@locdoremon Its already there. :)

@chai2champ

This comment has been minimized.

Copy link

@chai2champ 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

This comment has been minimized.

Copy link

@rajmiglani rajmiglani commented Oct 31, 2014

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

@kaustubhkulkarni05

This comment has been minimized.

Copy link

@kaustubhkulkarni05 kaustubhkulkarni05 commented Jan 29, 2015

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

@MayankPratap

This comment has been minimized.

Copy link

@MayankPratap 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

This comment has been minimized.

Copy link

@skmohit05 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

This comment has been minimized.

Copy link

@yash9499 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

This comment has been minimized.

Copy link

@yash9499 yash9499 commented Oct 5, 2016

please help me find error

@aditya81070

This comment has been minimized.

Copy link

@aditya81070 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

This comment has been minimized.

Copy link

@NishithaDundigala NishithaDundigala commented Dec 13, 2017

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

@GunjanPardal

This comment has been minimized.

Copy link

@GunjanPardal 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

This comment has been minimized.

Copy link

@unique-versal unique-versal commented Oct 22, 2018

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

@N01Z3B0t

This comment has been minimized.

Copy link

@N01Z3B0t N01Z3B0t commented Mar 11, 2019

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

@swapnil1505

This comment has been minimized.

Copy link

@swapnil1505 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

This comment has been minimized.

Copy link

@Aditya-Ojha 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

This comment has been minimized.

Copy link

@uvedkhan uvedkhan commented Sep 13, 2020

Best Data Structure implementation so far

@ravi8190

This comment has been minimized.

Copy link

@ravi8190 ravi8190 commented Sep 30, 2020

how to manage this code for user inputs

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