Program to Create Binary Search Tree (BST) and Searching a Specific Value in BST

In This Post We Cover How to Create Binary Search Tree (BST) and Searching a Specific Value in BST in C++ Step by Step

Source Code :

#include<iostream>

#include <windows.h>

using namespace std;

void gotoxy(int x, int y) {

COORD pos = {x, y};

SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);

}

struct Node{

int n;

Node *righNode,*leftNode;

};

class BST{

private:

Node *start,*currnt,*tmp;  

public:

//Constructor of BST class

BST(){

start = NULL;

}

//Create BST Method Start Here

void CreateBST(int data){

int col = 40, row = 1;

if(start==NULL){

start = new Node;

start->n = data;

start->leftNode = start->righNode = NULL;

gotoxy(col,row);

cout<<data;

}

else{

Node *parent;  // Parent

    currnt = start;

while(currnt!=NULL){

if(currnt->n == data){

cout<<"Data Already Exits"<<endl;

return;

}

if(currnt->n<data){

parent = currnt;

currnt = currnt->righNode;

row+=2;

col+=6;

}

else{

parent = currnt;

currnt = currnt->leftNode;

row+=2;

col-=6;

}

} 

tmp = new Node;

tmp->n = data;

tmp->leftNode = tmp->righNode = NULL;

gotoxy(col,row);

cout<<data;

if(parent == NULL)

     parent = tmp;

else if(parent->n > data)

     parent->leftNode = tmp;

     else

     parent->righNode = tmp;

}

}

// Search Function in Binary Tree  

Node* search(Node* s, int tr){

s = start;

if(s == NULL){

cout<<"Tree is Empty";

}

else{

currnt = s;

while(currnt!=NULL){

if(currnt->n==tr){

return currnt;

}

if(currnt->n<tr)

   currnt = currnt->righNode;

else

   currnt = currnt->leftNode;

}

}

return currnt;

} 

};

main(){

BST obj1;

int len;

cout<<"Enter Number of Nodes in Tree:";

cin>>len;

int arr[len];

for(int i =0; i<len; i++){

cin>>arr[i];

}

for(int i =0; i<len; i++)

obj1.CreateBST(arr[i]);

char choice;

do{

int val;

Node *res,*tr;

res = tr = NULL;

cout<<"\nEnter Value to Search:";

cin>>val;

res = obj1.search(tr, val);

if(res== NULL)

    cout<<"Node not found in this tree :"<<endl;

else 

    cout<<"Node found in this tree:"<<endl;

    cout<<"\nDo You Want to Continue [Y/N]:";

    cin>>choice;

}while(choice == 'Y'||choice == 'y');

}

Output