Search an element in Binary Search Tree using C++

The Binary search tree is a data structure consisting of nodes. The nodes are either null or have reference to other (child) nodes. Every node can have up to 2 nodes, called the left node or the right node. Each node will also contain a value, which will determine where these nodes are placed within the BST.

Just like a linked list, each node is referenced by only the other node; which is its parent node. The root node is the only node in the BT or BST which doesn’t have any parent node. The binary search tree is a binary tree data structure with the single property: The left sub-tree of a node has only nodes with a value less than the node’s value. Both the left and right subtrees must also be binary search trees.

C++ Binary Search Tree

void Search(node *root, int data)
{
	int depth = 0;
	node *temp = new node;
	temp = root;

	while(temp != NULL)
	{
		depth++;
		if(temp->data == data)
		{
			cout<<"\nElement found at depth: "<<depth;
			return;
		}

		else if(temp->data > data)
			temp = temp->left;

		else
			temp = temp->right;
	}

	cout<<"\n Not found";
	return;
}

How does the program work?

Let’s say, you already have a BST created from an array arr[10] ={4,5,7,2,7,4,6,3,5,7} .

This Binary search tree can be accessed via a node pointer root.

Just call the above function on the root node of the BST. If the number exists in BST, it will return the level/depth. Otherwise, it will display a text message “Not found.”

node *root = new node;
Search(root, number_to_be_found);

Recomanded reading