Element Searching in Binary Search Tree(BST)

For searching an specific data or element in BST is similar to Binary Search Algorithm.

• If searching data is less than the root , then we will go to left subtree for finding the required data , means we will not include right subtree in searching.
• If searching data is greater than the root , then we will go to the right subtree for finding the required data.
• But if searching data is found at root then we will stop the searching process.

Working Process

• In the Below BST , if we want to find out the data element 50. then we will follow the below strategy :

Code Implementation

• To search an element in Binary Search Tree , we can implement this functionality by two ways :
  1 -: Recursive Code Implementation.
  2 -: Non-Recursive Code Implementation.

1 -: Recursive Code Implementation

Here root is the BST and we want to search searching_Data in BST.

void ElementSearchInBST(BSTNode* root, int searching_Data)
{
	if (root == NULL)
		printf("Sorry searching data is not present in Binary Search Tree :");
	if (searching_Data == root->data)
         {
		printf("Required Element %d has been found....",searching_Data);
                return;
         }
	if (searching_Data < root->data)
		ElementSearchInBST(root->left,searching_Data);
	if (searching_Data > root->data)
		ElementSearchInBST(root->right,searching_Data);
}

2 -: Non-Recursive Code Implementation

void ElementSearchInBST(BSTNode* root, int searching_Data)
{
	if (root == NULL)
	{
		printf("Sorry searching data is not present in Binary Search Tree :");
		return;
	}
	while (root)
	{
		if (searching_Data == root->data)
			printf("Required Element %d has been found....", searching_Data);
		if (searching_Data < root->data)
			root = root->left;
		else
			root = root->right;
	}
}

 Time & Space Complexity

• Recursive & Non-Recursive Implementation Complexity :
  1 -: Worst Case Time Complexity : O(n).
  2 -: Average Case Time Complexity : O(logn).
  3 -: Best Case Time Complexity : O(1).
• Space Complexity :
  1 -: Recursive Implementation = O(n).
  2 -: No-Recursive Implementation = O(1).