Binary Search tree - Implementation in C++. Simple program to create a BST of integers and search an element in it

BST_CPP.cpp

// Binary Search Tree - Implemenation in C++
// Simple program to create a BST of integers and search an element in it 
#include<iostream>
using namespace std;
//Definition of Node for Binary search tree
struct BstNode {
	int data; 
	BstNode* left;
	BstNode* right;
};

// Function to create a new Node in heap
BstNode* GetNewNode(int data) {
	BstNode* newNode = new BstNode();
	newNode->data = data;
	newNode->left = newNode->right = NULL;
	return newNode;
}

// To insert data in BST, returns address of root node 
BstNode* Insert(BstNode* root,int data) {
	if(root == NULL) { // empty tree
		root = GetNewNode(data);
	}
	// if data to be inserted is lesser, insert in left subtree. 
	else if(data <= root->data) {
		root->left = Insert(root->left,data);
	}
	// else, insert in right subtree. 
	else {
		root->right = Insert(root->right,data);
	}
	return root;
}
//To search an element in BST, returns true if element is found
bool Search(BstNode* root,int data) {
	if(root == NULL) {
		return false;
	}
	else if(root->data == data) {
		return true;
	}
	else if(data <= root->data) {
		return Search(root->left,data);
	}
	else {
		return Search(root->right,data);
	}
}
int main() {
	BstNode* root = NULL;  // Creating an empty tree
	/*Code to test the logic*/
	root = Insert(root,15);	
	root = Insert(root,10);	
	root = Insert(root,20);
	root = Insert(root,25);
	root = Insert(root,8);
	root = Insert(root,12);
	// Ask user to enter a number.  
	int number;
	cout<<"Enter number be searched\n";
	cin>>number;
	//If number is found, print "FOUND"
	if(Search(root,number) == true) cout<<"Found\n";
	else cout<<"Not Found\n";
}

c++ code without recursion:

#include <iostream>
using namespace std;

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

Node *newNode(int key)
{
    Node *node = new Node;
    node->data = key;
    node->left = node->right = nullptr;

    return node;
}

void insert(Node **headref, int data)
{

    if (*headref == NULL)
    {
        *headref = newNode(data);
        return;
    }

    Node *travptr = *headref;
    Node *parentNode = NULL;

    while (travptr != NULL)
    {
        parentNode = travptr;
        travptr = (data > travptr->data) ? travptr->right : travptr->left;
    }

    if (data > parentNode->data)
        parentNode->right = newNode(data);

    else
        parentNode->left = newNode(data);
}

bool find(Node **headref, int data)
{
    Node *travptr = *headref;

    if (data == (*headref)->data)
        return true;

    while (travptr != NULL && travptr->data != data)
        travptr = (data > travptr->data) ? travptr->right : travptr->left;

    if (travptr == NULL)
    {
        return false;
    }
    return true;
}

int main()
{

    Node *head = NULL;
    insert(&head, 1);
    insert(&head, 2);
    insert(&head, 3);
    insert(&head, 4);
    cout << find(&head, 3) << "\t" << find(&head, 10);
    return 0;
}

And c++ code with recursion:

#include<iostream>
using namespace std;

struct Node{
    int data;
    Node *left,*right;
};


Node *newNode(int key)
{
    Node *node = new Node;
    node->data = key;
    node->left = node->right = nullptr;

    return node;
}

void insert(Node* &travptr, int data){

    if (travptr == nullptr)
    {
        travptr = newNode(data);
        return;
    }
    (data > travptr->data)? insert(travptr->right,data) : insert(travptr->left, data);
    
}

bool contains(Node* travptr, int data){

    if (travptr == nullptr)
    {  
        return false;
    }
    if (data == travptr->data)
    {
        return true;
    }

    return (data > travptr->data) ? contains(travptr->right, data) : contains(travptr->left, data);
    
}

int main()
{
    Node* root = nullptr;

    insert(root, 1);
    insert(root, 2);
    insert(root, 3);
    insert(root, 4);
    insert(root, 5);

    cout << contains(root, 3) << "\t" << contains(root, 10) << "\t" << contains(root, 5);
    
    return 0;
}

Thanks. Videos are explained nicely.

well explained sir ..thank you so so much :)

Hello, I had written a code by introducing root as a global variable. But the code isn't running. It would be very helpful if someone could help me out.

#include
#include
#include

using namespace std;

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

Node* root;

Node* GetNewNode(int data){
Node* fresh = new Node();
fresh->data = data;
fresh->left = NULL;
fresh->right = NULL;
return fresh;
}

void Insert(Node* ins,int data){
Node* temp = GetNewNode(data);
if(ins == NULL){
ins = temp;
cout<<"Insert NULL\n";
}
else if(data<=ins->data) {
cout<<"Insert Left\n";
Insert(ins->left,data);

}	
else {
cout<<"Insert Right\n";	
Insert(ins->right,data);

}

}

bool Search(Node*s,int data){
if(s == NULL) return false;
else if(s->data == data) return true;
else if(s->data>=data) return Search(s->left,data);
else return Search(s->right,data);
}

int main(){
int n;
root = NULL;
Insert(root,5);
Insert(root,6);
Insert(root,3);
cout<<"Search for the number\n";
cin>>n;
if(Search(root,n) == true) cout<<"Found\n";
else cout<<"Not Found\n";
}

you have to call Insert function Pass By Reference as you have taken root variable global.
Hope this works.

It would be very helpful if you could send the "Insert Function" Snippet as I am not able to understand your comment

Thanks

the function is here ....enjoy

Node* Insert(Node* &ins, int data)
{
if (ins == NULL) return GetNewNode(data);

if (data <= ins->data)
	ins->left = Insert(ins->left, data);

else if (data > ins->data)
	ins->right = Insert(ins->right, data);

return ins;

}

Nice explanation .

Implementation in C++ using class:

#include <iostream>
class BSTNode
{
private:
	int data;
	BSTNode* left;
	BSTNode* right;
public:
	BSTNode(int data)
	{
		this -> data = data;
		this -> left = NULL;
		this -> right = NULL;
	}
	~BSTNode();

	void insert(int data)
	{
		if (data <= this -> data)
		{
			if (this -> left == NULL)
			{
				this -> left = new BSTNode(data);
			}
			else
			{
				this -> left -> insert(data);
			}
		}
		else
		{
			if (this -> right == NULL)
			{
				this -> right = new BSTNode(data);
			}
			else
			{
				this -> right -> insert(data);
			}
		}
		
	}

	void print_node ()
	{
		std::cout << "Value at the node: " << this -> data << std::endl;
		if (this -> left != NULL)
			std::cout << "Value at left node: " << this -> left -> data << std::endl;
		if (this -> right != NULL)
			std::cout << "Value at right node: " << this -> right -> data << std::endl;
	}

	bool find(int val)
	{
		if (this -> data == val)
		{
			std::cout << "Found" << std::endl;
			return true;
		}
		else if (val <= this -> data)
		{
			if (this -> left == NULL)
			{
				std::cout << "Not found" << std::endl;
				return false;
			}
			else
			{
				return (this -> left) -> find(val);	
			}
		}
		else
		{
			//std::cout << "It's here" << std::endl;
			if (this -> right == NULL)
			{
				std::cout << "Not found" << std::endl;
				return false;
			}
			else
			{
				//std::cout << "passing" << std::endl;
				return (this -> right) -> find(val);	
			}
		}
		std::cout << "Something wrong while trying to find" << std::endl;
		return false;
	}
};


int main()
{
	BSTNode* root = new BSTNode(10);
	root -> print_node();
	root -> insert(9);
	root -> insert(7);
	root -> insert(6);
	root -> print_node();
	root -> insert(14);
	root -> print_node();
	std::cout << "Finding 10: " << root -> find(10) << std::endl;
	std::cout << "Finding 8: " << root -> find(8) << std::endl;
	root -> insert(19);
	root -> insert(70);
	root -> insert(3);
	root -> print_node();
	root -> insert(4);
	root -> insert(8);
	root -> print_node();
	std::cout << "Finding 70: " << root -> find(70) << std::endl;
	std::cout << "Finding 8: " << root -> find(8) << std::endl;
	std::cout << "Finding 17: " << root -> find(17) << std::endl;
}

how to write DeleteNode Code

Best explanation.

root = Insert(root,15);
root = Insert(root,10);
root = Insert(root,20);
root = Insert(root,25);
root = Insert(root,8);
root = Insert(root,12);

Why are we re-assigning root? you said we can only have 1 root in the BST

well same question in my mind

@keshav-kabra i also have the same doubt bro...........i dont what value is assigned to the root each time the function call is made????

bool contains(Node* travptr, int data){

if (travptr == nullptr)
{  
    return false;
}
if (data == travptr->data)
{
    return true;
}

(data > travptr->data) ? contains(travptr->right, data) : contains(travptr->left, data);

}

@vigneshwar221B may I know why it doesn't work when I omit the word 'return'?

root = Insert(root,15);
root = Insert(root,10);
root = Insert(root,20);
root = Insert(root,25);
root = Insert(root,8);
root = Insert(root,12);
Why are we re-assigning root? you said we can only have 1 root in the BST

well same question in my mind

because root is a local variable and in the insert function, it is the root which is manipulated and returned. So, we have to update root that's why re-assigning

does anybody know how to create print function without this operator

can you explain why we are returning root in insert ?

to ,store value in main root variable (node)

@keshav-kabra i also have the same doubt bro...........i dont what value is assigned to the root each time the function call is made????

every time we call root beacause every time root store its previous node's value .
watch this video for more inforamation ...
https://www.youtube.com/watch?v=COZK7NATh4k&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P&index=28

Can anyone give me the non-recursive code in C++??

U can find a full non recursive code here...
https://github.com/keshav-kabra/DataStructures/blob/master/BST.cpp

I have a doubt in this lecture that I saw on YouTube. Whenever you initialize a node how do u ensure that its left and right pointers are initialized to NULL ?

The constructor GetNewNode does the work. Even if you don't make a constructor the default values for the pointer will be null itself.

my implementation in C using loop and global variables. advice is much appreciated

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

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

struct BstNode *rootPtr;

struct BstNode *GetNewNode(int data)
{
struct BstNode *newNode = (struct BstNode *)malloc(sizeof(struct BstNode));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}

void Insert(int data)
{
if (rootPtr == NULL)
{
rootPtr = GetNewNode(data);
return;
}
struct BstNode *temp2 = rootPtr;
while (temp2->left != NULL || temp2->right != NULL)
{
if (data < temp2->data)
temp2 = temp2->left;
else
temp2 = temp2->right;
}

if (data > temp2->data)
{
    temp2->right = GetNewNode(data);
    return;
}
else
{
    temp2->left = GetNewNode(data);
    return;
}

}
_Bool FindElement(int data)
{

struct BstNode *temp = rootPtr;
while (temp->data != data)
{
    if (data < temp->data)
    {
        temp = temp->left;
    }
    else
    {
        temp = temp->right;
    }
}

if (temp == NULL)
{
    return false;
}
else
{
    return true;
}

}

int main()
{
rootPtr = NULL;
Insert(12);
Insert(13);
Insert(14);
Insert(16);
printf("\n");
if (FindElement(16))
{
printf("We found the value\n");
}
else
{
printf("We could not find the value\n");
}
}`

I have a doubt in this lecture that I saw on YouTube. Whenever you initialize a node how do u ensure that its left and right pointers are initialized to NULL ?

its mentioned in the getnewnode function

Great explanation!!! Thank you :)

Great explanation... Thank you very much

I have a doubt in this lecture that I saw on YouTube. Whenever you initialize a node how do u ensure that its left and right pointers are initialized to NULL ?

Because in GetNode function that is assigned as null everytime

Why search function is not working in my VS code? Neither "found" nor "not found" is printing

sir BstNode* newNode = new BstNode(); this BstNode() must be class name so how can u use struct name as class name??

Yes, you can also create class in C++. But there is no problem in using structure you can use class for simplicity of code:
class bstNode {
public:
int data;
bstNode* left;
bstNode *right;
}
Now you can create a node using :
bstNode *temp = new bstNode;
Yes using class code will reduce.

root = Insert(root,15);
root = Insert(root,10);
root = Insert(root,20);
root = Insert(root,25);
root = Insert(root,8);
root = Insert(root,12);

Why are we re-assigning root? you said we can only have 1 root in the BST

We are not reassigning the root .... root is same throughout the program.
Check for recursive call in detail then you will know the reason.

C implementation with free memory

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

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

BstNode* BstNode_create(int data) {
    BstNode *rPtr = (BstNode*)malloc(sizeof(BstNode));
    rPtr->data = data;
    rPtr->left = NULL;
    rPtr->right = NULL;
    return rPtr;
}

void BstNode_insert(BstNode **node, int data) {
    if (*node == NULL) {
        *node = BstNode_create(data);
    } else if (data > (*node)->data) {
        BstNode_insert(&(*node)->right, data);
    } else {
        BstNode_insert(&(*node)->left, data);
    }
}

BstNode *BstNode_search(BstNode *node, int data) {
    if (node == NULL) {
        return NULL;
    } else if (data == node->data) {
        return node;
    } else if (data > node->data) {
        return BstNode_search(node->right, data);
    } else {
        return BstNode_search(node->left, data);
    }
}

void BstNode_destroy(BstNode **node) {
    if ((*node)->left != NULL) {
        BstNode_destroy(&(*node)->left);
    }

    if ((*node)->right != NULL) {
        BstNode_destroy(&(*node)->right);
    }

    free(*node);
    *node = NULL;
}

int main() {
    BstNode *root = BstNode_create(10);
    BstNode_insert(&root, 3);
    BstNode_insert(&root, 11);
    BstNode_insert(&root, 5);
    BstNode_insert(&root, 14);
    BstNode_insert(&root, 9);
    BstNode_insert(&root, 13);

    const int MAX_SEARCH = 5;
    int numbers[MAX_SEARCH];
    numbers[0] = 5;
    numbers[1] = 8;
    numbers[2] = 13;
    numbers[3] = 9;
    numbers[4] = 22;

    BstNode *found_node;

    for (int i = 0; i < MAX_SEARCH; ++i) {
        printf("searching [%d] ", numbers[i]);

        found_node = BstNode_search(root, numbers[i]);
        printf("%s.\n", found_node != NULL ? "found" : "not found");
    }

    BstNode_destroy(&root);

    return EXIT_SUCCESS;
}

to help check memory leak

valgrind --leak-check=full -v ./your_program

for all those whose are confusing about the root node ,,
here the root is not varying every time we call the insert function it is only changed when the root node is empty , in all the other cases we are just returning the nodes which are pointing left subtree or right subtree .
BstNode* GetNewNode(int data) {
BstNode* newNode = new BstNode();
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}

// To insert data in BST, returns address of root node
BstNode* Insert(BstNode* root,int data) {
if(root == NULL) { // empty tree
root = GetNewNode(data);
}
// if data to be inserted is lesser, insert in left subtree.
else if(data <= root->data) {
root->left = Insert(root->left,data);
}
// else, insert in right subtree.
else {
root->right = Insert(root->right,data);
}
return root;
as we can see here if a given value is less than the root node value then it goes to else if condition and then it calls to a recursive function in which it takes the parameters as left subtree node instead of root node as in the if case and then it creates a node for left subtree, such that we will get the left subtree node as return node which is then assigned to the root->left value .
root->left = Insert(root->left,data);
but at last we return the node which is a node of root
return root;
hence here the root node is always fixed for the root of the tree and here we are passing it through the function just to access the tree and in the case of head in a linked list .