Search a Node in a Binary search tree in C++

Searching in binary search tree

 

Here in this section , we will discuss the C++ program to search a node in binary search tree. Searching in Binary Search tree is the most basic program that you need to know, it has some set of rules that you need to follow, given below .

Binary Search Tree

Algorithm : 

Consider the value that you need to search in a Binary search tree is called as data.

  • Start from the root node of BST
  • If the (root node value) == data, value found
  • Else, if (root node value) > data, then iterate to the left subtree
  • Else if (root node value) < data, then iterate to the right subtree
  • Keep on doing this until you find the value
Searching a node in binary search tree

C++ Program Based on above Algorithm :

#include <bits/stdc++.h>
using namespace std;


// Struct of Tree
struct node
{
int val;
struct node *left, *right;
};

// Function to create a new Node
struct node *newNode (int data)
{
struct node *temp = (struct node *) malloc (sizeof (struct node));
temp->val = data;
temp->left = temp->right = NULL;

return temp;
}

// Function to check if a given node exists in a binary search tree or not
int search (struct node *root, int value)
{
// while is used to traverse till the end of tree
while (root != NULL)
{
// checking condition and passing right subtree & recusing
if (value > root->val)
root = root->right;

// checking condition and passing left subtree & recusing
else if (value < root->val)
root = root->left;

else
return 1; // if the value is found return 1
}

return 0;
}


int main ()
{
/*Root is created first */
struct node *root = newNode (21);

root->left = newNode (16);
root->right = newNode (25);
root->left->left = newNode (10);
root->left->right = newNode (18);
root->right->left = newNode (22);
root->right->right = newNode (28);
root->left->left->left = newNode (8);
root->left->left->right = newNode (12);

int search = 10;

// Function to find item in the tree
int found = search (root, search);

if (found)
cout << search << " value is found in the tree";

else
cout << search << " value not found";

return 0;
}
Output :

10 value is found in the tree.