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: