my code stock.com

My First project on Algorithims
Binary Search Tree

Opration
- Sorting ( inorder)
- pre order
- post order
- Search ( specific node)
- Deletion
  * Specifice node
  * All tree
- Size of BST
- Sum of BST
- Max of BST
- Min of BST

Snippet options

Download: Download snippet as bst.cpp.
Copy snippet: For this you need a free my code stock.com account.
Embed code : You will find the embed code for this snippet at the end of the page, if you want to embed it into a website or a blog!

#include<iostream>
#include<stdlib.h>
#include<process.h>
using namespace std;

struct NODE{
	int info;
	NODE *Left; 
	NODE *Right; 
};

NODE *Root = NULL;

void AttachNode(NODE *pRoot,NODE *pNew){
	if (Root == NULL)
	{
		Root = pNew; return; 
	}
	if (pNew->info < pRoot->info) //if info of new node less than info of root
	{    //traverse to Left sub-tree and find null at Left
		if (pRoot->Left != NULL)//
			AttachNode(pRoot->Left, pNew);// recarsive call
		else
			pRoot->Left = pNew; //set a node in the Left
	}
	else
	{
		//traverse to Right sub-tree and find null at Right
		if (pRoot->Right != NULL)
			AttachNode(pRoot->Right, pNew); // recarsive call
		else
			pRoot->Right = pNew; //set a node in the Right
	}

}

 //////////// create node /////////////////
void Insert(int x)
{
	NODE *NewNode = new NODE;

	NewNode->Left = NULL; 
	NewNode->Right = NULL; 
	NewNode->info = x; 
	AttachNode(Root, NewNode);//insert newnode in the tree

}


//////////// size of tree/////////////
int size(NODE *pRoot) 
{
	if (pRoot == NULL)
		return 0;
	else
		return(size(pRoot->Left) + 1 + size(pRoot->Right));
}


/////////// sum of the element on the tree /////////////
int sum(NODE *pRoot) 
{
	if (pRoot == NULL)
		return 0;
	else
		return pRoot->info + sum(pRoot->Left) + sum(pRoot->Right);
}


/////////// in order traverser ////////////
void  In_Order(NODE *pRoot) //Left Root Right
{
	if (pRoot)
	{
		In_Order(pRoot->Left);//call with Left node
		cout << pRoot->info << "\t"; // print the root
		In_Order(pRoot->Right); // call with the Right node
	}
}



void Pre_Order(NODE *pRoot)
{
	if (pRoot)
	{
		cout << pRoot->info << "\t";
		Pre_Order(pRoot->Left);
		Pre_Order(pRoot->Right);
	}
}

void   Post_Order(struct NODE *pRoot)
{
	if (pRoot)
	{
		Post_Order(pRoot->Left);
		Post_Order(pRoot->Right);
		cout << pRoot->info << "\t";
	}
}

////////////// level of each node /////////////
void display(NODE *pRoot, int level)
{
	int i;

	if (!pRoot) return;


	for (i = 0; i<level; ++i) cout << " ";
	cout << "\n---------\nR" << i;
	cout << "\n" << pRoot->info;
	display(pRoot->Right, level + 1);
	display(pRoot->Left, level + 1);
	cout << endl;

}



///////////// search specific node ///////////////
NODE *Find(NODE *pRoot, int item)
{
	if (pRoot == NULL) // if  tree is empty return 0
	{
		return 0;
	}
	if (item > pRoot->info) //cheak if item is grater than root
	{

		return Find(pRoot->Right, item);// item may found in right subtree
	}
	else if (item < pRoot->info) //cheak if item is less than root
	{

		return Find(pRoot->Left, item); //item may found in the left subtree
	}
	else
	{
		return pRoot;
	}
}

//////////// find Min element on BST ///////////
NODE *FindMin(NODE *pRoot)
{
	if (pRoot == NULL)// if tree is empty return null
	{
		return NULL;
	}
	if (pRoot->Left) // pointer to left subtree 
		return FindMin(pRoot->Left);// find the min left subtree
	else
		return pRoot;
}

////////////// find max on BST ///////////////
NODE *FindMax(NODE *pRoot){
	if (pRoot == NULL)
	{
		return NULL;
	}
	if (pRoot->Right)
		return FindMax(pRoot->Right);
	else
	return pRoot;

}

//////////// delete specific node /////////////
NODE  *Delete(NODE *pRoot, int item)
{
	NODE *temp;
	if (pRoot == NULL)
	{
		cout << "tree is empty";
	}
	else if (item < pRoot->info) //cheak if item to be deleted is less than the root
	{
		pRoot->Left = Delete(pRoot->Left, item); //delete item if found in the left subtree
	}
	else if (item > pRoot->info) // cheak if item to be deleted is grater than the root
	{
		pRoot->Right = Delete(pRoot->Right, item); // delete item if found in the right subtree
	}
	else
	{

		// here if we delete node and rplace with min element in right subtree or max element in the left subtree
		if (pRoot->Right && pRoot->Left)
		{
			temp = FindMin(pRoot->Right);// replace with minimum element in the right subtree  
			pRoot->info = temp->info;//initl the root to temp
			pRoot->Right = Delete(pRoot->Right, temp->info);//replaced it with some other node, we have to delete that node  
		}
		else
		{

			temp = pRoot;
			if (pRoot->Left == NULL)// if left subtree is empty
				pRoot = pRoot->Right; //go to right subtree
			else if (pRoot->Right == NULL) //if right subtree is empty
				pRoot = pRoot->Left; //go to left subtree
			free(temp); // temp is longer required 
		}
	}
	return pRoot;

}

/////////////////////// delete all tree ////////////////
void deletetree(NODE *pRoot){
	if (pRoot)
	{
		if (pRoot->Left)
			deletetree(pRoot->Left);
		if (pRoot->Right);
	}
	delete pRoot;
}




int main(void)
{
	int item;
	NODE * temp;



	cout << "***i20***\n"; cin >> item;
	Insert(item);
	display(Root, 1);

	cout << "\n***i50***\n"; cin >> item;
	Insert(item);
	display(Root, 1);

	cout << "\n***i30***\n"; cin >> item;
	Insert(item);
	display(Root, 1);


	cout << "\n***f 50 *** \n"; cin >> item;
	temp = Find(Root, item);
	if (temp == NULL)
	{
		cout << "\n not found\n";
	}
	else
	{
		cout << "\n Found\n " << item;
	}


	cout << "\n***i70***\n"; cin >> item;
	Insert(item);
	display(Root, 1);



	cout << "\n***f 100*** \n"; cin >> item;
	temp = Find(Root, 1);
	if (temp == NULL)
	{
		cout << " not found\n";
	}
	else
	{
		cout << "Found\n " << item;
	}





	cout << "\n***i5***\n"; cin >> item;
	Insert(item);
	display(Root, 1);

	cout << "\n***i100***\n"; cin >> item;
	Insert(item);
	display(Root, 1);




	cout << "\n***r50***\n"; cin >> item;
	Root = Delete(Root, item);
	display(Root, 1);


	cout << "\n\nsize is:" << size(Root);

	cout << "\n\n***i110***\n"; cin >> item;
	Insert(item);
	display(Root, 1);

	cout << "\n\n***t***\n";
	In_Order(Root);

	cout << "\n\n";
	cout << "\n***r30***\n\n"; cin >> item;
	Root = Delete(Root, item);
	display(Root, 1);

	cin >> item;


}

Create a free my code stock.com account now.

my code stok.com is a free service, which allows you to save and manage code snippes of any kind and programming language. We provide many advantages for your daily work with code-snippets, also for your teamwork. Give it a try!

Find out more and register now

You can customize the height of iFrame-Codes as needed! You can find more infos in our API Reference for iframe Embeds.