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

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