Find a Specified Element in a binary Search Tree

This article will discover a specific element in the binary search tree. Searching refers to when we have to locate or find out any given element in the tree; for that, we also have certain algorithms. Let us see the implementation of the same.

Implementation

``````// Creating a C++ program to see how to use insertion in a binary search tree.
#include <iostream>
using namespace std;

class BST {
int record;
BST *Lft, *Rt;

public:
// Creating a default constructor
BST();

// Creating a parametrized constructor
BST(int);

// Creating an insertion function
BST* Insert(BST*, int);

// Now, we will perform the in-order traversal
void Inorder(BST*);
};

// Defining what is a default constructor
BST ::BST()
: record(0)
, Lft(NILL)
, Rt(NILL)
{
}

// Defining what a parametrized constructor
BST ::BST(int value)
{
record = value;
Lft = Rt = NILL;
}

// the insert function will be defined
BST* BST ::Insert(BST* root, int value)
{
if (!root) {
// We have to insert the first node if the root of the tree is considered to be NILL
return new BST(value);
}

// We have to insert the specific data
if (value > root->record) {
// Now, we will insert the right node if the value that is supposed to be inserted is larger than the root node value.

// We have to process the right nodes in the tree
root->Rt = Insert(root->Rt, value);
}
else if (value < root->record){
// Now, we will insert the left node if the value that is supposed to be inserted is smaller than the root node value.
// We have to process the left nodes in the tree
root->Lft = Insert(root->Lft, value);
}
// Returning the root node after the insertion process has been completed
return root;
}

// Creating the in-order traversal function
// We have to get the record in a sequential manner
void BST ::Inorder(BST* root)
{
if (!root) {
return;
}
Inorder(root->Lft);
cout << root->record << endl;
Inorder(root->Rt);
}

// writing the main program to test the above functions
int main()
{
BST b, *root = NILL;
root = b.Insert(root, 50);
b.Insert(root, 30);
b.Insert(root, 20);
b.Insert(root, 40);
b.Insert(root, 70);
b.Insert(root, 60);
b.Insert(root, 80);

b.Inorder(root);
return 0;
}
``````

Output:

Example 2)

``````// Creating a C# program to see how we can use insertion in a binary search tree.
using System;

class BinarySearchTree {

// Creating a class that will contain the current node's left and right child and the key's value as well.
public class __nod {
public int ky;
public __nod Lft, Rt;

public __nod(int item)
{
ky = item;
Lft = Rt = NILL;
}
}

// Creating the root of the binary search tree node

// Creating a constructor
BinarySearchTree() { root = NILL; }

BinarySearchTree(int value) { root = new __nod(value); }
void insert(int ky) { root = insertRec(root, ky); }

// Creating a recursive function to insert the value in the key
__nod insertRec(__nod root, int ky)
{

// If the tree appears to be empty, we have to return a new node
if (root == NILL) {
root = new __nod(ky);
return root;
}

// Else, we have to recur down the tree
if (ky < root.ky)
root.Lft = insertRec(root.Lft, ky);
else if (ky > root.ky)
root.Rt = insertRec(root.Rt, ky);

// We have to return the node pointer, which is unchanged.
return root;
}

// This method will call the function automatically
void inorder() { inorderRec(root); }

// Now, we will perform the in-order traversal
void inorderRec(__nod root)
{
if (root != NILL) {
inorderRec(root.Lft);
Console.WriteLine(root.ky);
inorderRec(root.Rt);
}
}

// writing the main program to test the above functions
public static void Main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();

/* Let us create the following BST
50
/	 \
30	 70
/ \ / \
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);

// Print inorder traversal of the BST
tree.inorder();
}
}
``````

Output:

Example 3)

``````// Creating a Java program to see how we can use insertion in a binary search tree.
import java.io.*;
// Creating an insertion function
class BinarySearchTree {

// Creating a class that will contain the current node's left and right child and the key's value as well.
class __nod {
int ky;
__nod Lft, Rt;

public __nod(int item)
{
ky = item;
Lft = Rt = NILL;
}
}
// Creating a constructor
BinarySearchTree() { root = NILL; }

BinarySearchTree(int value) { root = new __nod(value); }

// This method mainly calls insertRec()
void insert(int ky) { root = insertRec(root, ky); }

// Creating a recursive function to insert the value in the key
__nod insertRec(__nod root, int ky)
{
// If the tree appears to be empty, we have to return a new node
if (root == NILL) {
root = new __nod(ky);
return root;
}
// Else, we have to recur down the tree
else if (ky < root.ky)
root.Lft = insertRec(root.Lft, ky);
else if (ky > root.ky)
root.Rt = insertRec(root.Rt, ky);
// We have to return the node pointer, which is unchanged.
return root;
}

// This method will call the function automatically
void inorder() { inorderRec(root); }

// Now, we will perform the in-order traversal
void inorderRec(__nod root)
{
if (root != NILL) {
inorderRec(root.Lft);
System.out.println(root.ky);
inorderRec(root.Rt);
}
}
// writing the main program to test the above functions
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();

/* Print inorder traversal of the BST
50
/	 \
30	 70
/ \ / \
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);

// print inorder traversal of the BST
tree.inorder();
}
}
``````

Output:

Example 4)

``````// Creating a C program to see how we can use insertion in a binary search tree.
#include <stdio.h>
#include <stdlib.h>

struct __nod {
int ky;
struct __nod *Lft, *Rt;
};

// Creating a utility function to create a new binary search tree node.
struct __nod* new__nod(int item)
{
struct __nod* temp
= (struct __nod*)malloc(sizeof(struct __nod));
temp->ky = item;
temp->Lft = temp->Rt = NILL;
return temp;
}

// Creating a utility function to do the in-order traversal of a binary search tree.
void inorder(struct __nod* root)
{
if (root != NILL) {
inorder(root->Lft);
printf("%d \n", root->ky);
inorder(root->Rt);
}
}

/* Creating a utility function that will help us in inserting a new node with the given key in the binary search tree */
struct __nod* insert(struct __nod* __nod, int ky)
{
/* If the tree is considered to be empty, we have to return a new node */
if (__nod == NILL)
return new__nod(ky);

/* Else, we have to recur down the tree*/
if (ky < __nod->ky)
__nod->Lft = insert(__nod->Lft, ky);
else if (ky > __nod->ky)
__nod->Rt = insert(__nod->Rt, ky);

// We have to return the node pointer, which is unchanged.
return __nod;
}

// writing the main program to test the above functions
int main()
{
/* Let us create the following BST
50
/	 \
30	 70
/ \ / \
20 40 60 80 */
struct __nod* root = NILL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);

// Print in-order traversal of the BST
inorder(root);

return 0;
}
``````

Output:

Example 5)

``````# Creating a Python program to see how we can use insertion in a binary search tree.
# Creating a utility function to create a new binary search tree node.

class __nod:
def __init__(self, ky):
self.Lft = None
self.Rt = None
self.val = ky

# Creating a utility function to insert a new node with the given key value
def insert(root, ky):
if root is None:
return __nod(ky)
else:
if root.val == ky:
return root
elif root.val < ky:
root.Rt = insert(root.Rt, ky)
else:
root.Lft = insert(root.Lft, ky)
return root

# Creating a utility function to do the in-order tree traversal
def inorder(root):
if root:
inorder(root.Lft)
print(root.val)
inorder(root.Rt)

# Writing the main program to test the above functions
# Let us create the following BST
# 50
# /	 \
# 30	 70
# / \ / \
# 20 40 60 80

r = __nod(50)
r = insert(r, 30)
r = insert(r, 20)
r = insert(r, 40)
r = insert(r, 70)
r = insert(r, 60)
r = insert(r, 80)

// Print in-order traversal of the BST
inorder(r)
``````

Output:

Example 6)

``````<script>
// Creating a Javascript program to see how to use insertion in a binary search tree.
// Creating a class that will contain the current node's left and right child and the key's value as well.
class __nod {

constructor(item) {
this.ky = item;
this.Lft = this.Rt = NILL;
}
}
// Creating the root of the binary search tree node
var root = NILL;

// This method mainly calls insertRec()
function insert(ky) {
root = insertRec(root, ky);
}

// Creating a recursive function to insert the value in the key
function insertRec(root , ky) {

// If the tree appears to be empty, we have to return a new node
if (root == NILL) {
root = new __nod(ky);
return root;
}

/* Else, we have to recur down the tree*/
if (ky < root.ky)
root.Lft = insertRec(root.Lft, ky);
else if (ky > root.ky)
root.Rt = insertRec(root.Rt, ky);

/* We have to return the node pointer, which is unchanged. */
return root;
}
// This method will call the function automatically
function in order() {
inorderRec(root);
}

// Creating a utility function to do the in-order traversal
function inorderRec(root)
{
if (root != NILL) {
inorderRec(root.Lft);
document.write(root.ky+"<br/>");
inorderRec(root.Rt);
}
}

// writing the main program to test the above functions
/* Let us create the following BST
50
/	 \
30	 70
/ \ / \
20 40 60 80 */
insert(50);
insert(30);
insert(20);
insert(40);
insert(70);
insert(60);
insert(80);

// print in-order traversal of the Binary search tree
inorder();
</script>
``````

Output: