Searching In Binary Search Tree In C (2024)

Last Updated on June 30, 2023 by Mayank Dham

Searching In Binary Search Tree In C (1)

A binary search tree (BST) is a basic data structure that allows for fast searching, insertion, and deletion. Searching in a BST involves finding a specific key or value within the tree. In this article, we will explore how to perform searching in a binary search tree using the C programming language. We will cover the basic concepts, provide implementation details, and provide example code.

What is a Binary Search Tree (BST)?

A binary search tree is a binary tree data structure where each node has a key (or value) and two children, commonly referred to as the left child and the right child. The key in each node follows a specific order, such that the key in the left child is smaller than the key in the parent node, and the key in the right child is greater than the key in the parent node. This property allows for efficient searching, as it enables a divide-and-conquer approach.

Searching In Binary Search Tree In C (2)

Searching Algorithm in Binary Search Tree

The searching algorithm in a binary search tree follows a recursive approach based on the key values. Here are the steps involved in searching for a specific key in a binary search tree:

  • Start at the root node.
  • Compare the key value of the current node with the target key.
  • If the target key is found, return the node.
  • If the target key is smaller than the current node’s key, move to the left child and repeat the process.
  • If the target key is greater than the current node’s key, move to the right child and repeat the process.
  • If the target key is not found and there are no more nodes to explore, return NULL to indicate that the key is not present in the tree.

Implementation of Searching in Binary Search Tree in C

To implement searching in a binary search tree in C, we first need to define the structure for a tree node. Each node will have a key value, as well as pointers to its left and right children. Here is an example implementation of a binary search tree node in C:

typedef struct Node { int key; struct Node* left; struct Node* right;} Node;

Next, we can define a function to search for a key in the binary search tree recursively. The function will take the root node and the target key as parameters. Here is the implementation:

Node* search (Node* root, int key) { // Base case: If the tree is empty or the key is found if (root == NULL || root->key == key) { return root; } // If the key is smaller than the root's key, search in the left subtree if (key < root->key) { return search(root->left, key); } // If the key is greater than the root's key, search in the right subtree return search(root->right, key);}

Code Implementation of Searching in Binary Search Tree in C

Let’s consider a simple example to demonstrate the use of the search function. The key is 6

  • C
#include <stdio.h>#include <stdlib.h>// Structure for a BST nodestruct Node { int data; struct Node* left; struct Node* right;};// Function to create a new nodestruct Node* createNode(int value) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = value; newNode->left = NULL; newNode->right = NULL; return newNode;}// Function to insert a node into the BSTstruct Node* insert(struct Node* root, int value) { if (root == NULL) { return createNode(value); } if (value < root->data) { root->left = insert(root->left, value); } else { root->right = insert(root->right, value); } return root;}// Function to search for a value in the BSTstruct Node* search(struct Node* root, int value) { if (root == NULL || root->data == value) { return root; } if (value < root->data) { return search(root->left, value); } else { return search(root->right, value); }}int main() { // Input BST: [8,3,10,1,6,null,14,null,null,4,7,13,null] struct Node* root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 10); root = insert(root, 1); root = insert(root, 6); root = insert(root, 4); root = insert(root, 7); root = insert(root, 14); root = insert(root, 13); int key = 6; struct Node* result = search(root, key); if (result != NULL) { printf("Key %d found in the BST.\n", key); } else { printf("Key %d not found in the BST.\n", key); } return 0;}

Output
Key 6 found in the BST.

In the above example, we create a binary search tree with the given keys using the insert function. Then, we search for the key 6 using the search function. Since 6 is present in the tree, the output confirms its presence.

Conclusion
Searching in a binary search tree is an essential operation when working with this data structure. It allows us to efficiently locate specific keys within the tree. In this article, we covered the basic concept of searching in a binary search tree, provided a C implementation, and demonstrated an example usage. Understanding how to search in a binary search tree will enhance your ability to perform data retrieval tasks efficiently in your C programming projects.

Frequently Asked Questions (FAQs)

Q1. What is a Binary Search Tree (BST)?
A Binary Search Tree is a type of binary tree in which the values of the nodes are organized in a specific order. The key property of a BST is that the value of each node in the left subtree is less than the value of the node itself, and the value of each node in the right subtree is greater than the value of the node.

Q2. How does searching in a Binary Search Tree work?
To search for a value in a BST, we start from the root node and compare the value with the current node. If the value matches, the search is successful. If the value is less than the current node, we move to the left subtree. If the value is greater, we move to the right subtree. This process continues until we find the value or reach a leaf node.

Q3. What is the time complexity of searching in a Binary Search Tree?
In a balanced Binary Search Tree, the time complexity of searching is O(log n), where n is the number of nodes in the tree. This efficiency is achieved because the search space is divided in half at each step. However, in the worst-case scenario, when the tree is skewed and resembles a linked list, the time complexity of searching becomes O(n).

Q4. Can we search for a value in a Binary Search Tree iteratively instead of recursively?
Yes, searching in a BST can be implemented iteratively using a loop and a stack or queue data structure. The iterative approach is similar to the recursive approach, where we compare the value with the current node and traverse left or right accordingly. Instead of using function calls and recursion, we maintain a stack or queue to keep track of the nodes to be visited.

Q5. What happens if we search for a value that is not present in the Binary Search Tree?
When searching for a value that is not present in a BST, the search will continue until it reaches a leaf node where the value should have been found. At that point, the search will terminate, and we can conclude that the value is not present in the tree. This is indicated by returning a NULL value or a special marker to signify the absence of the value in the tree.

Searching In Binary Search Tree In C (2024)

FAQs

How to search through a binary tree in C? ›

To search for a value in a BST, we start from the root node and compare the value with the current node. If the value matches, the search is successful. If the value is less than the current node, we move to the left subtree. If the value is greater, we move to the right subtree.

How to do binary search in a binary search tree? ›

Lookup on a binary search tree is performed by traversing the tree down from the root and by choosing, at each step, if we want to continue by going right or left. We repeat this process until we find our value or the current node doesn't have a right/left child.

Which search algorithm is commonly used to search in a binary search tree? ›

Breadth-first search (BFS)

Breadth first search is an algorithm used to traverse a BST. It begins at the root node and travels in a lateral manner (side to side), searching for the desired node.

Does C have built in binary search? ›

Binary Search In C

A Binary Search is a sorting algorithm, that is used to search an element in a sorted array. A binary search technique works only on a sorted array, so an array must be sorted to apply binary search on the array.

What is the difference between binary searching and binary tree searching? ›

As often presented, binary search refers to the array based algorithm presented here, and binary search tree refers to a tree based data structure with certain properties. However, the properties that binary search requires and the properties that binary search trees have make these two sides of the same coin.

How to do binary search step by step? ›

How to write a Binary Search Algorithm?
  1. Initialization: Set low as the index of the first element in the array. ...
  2. Loop Condition: While low is less than or equal to high, continue the search.
  3. Comparison: If the element at the midpoint is equal to the target value, rturn the midpoint as the index. ...
  4. Repeat: ...
  5. Result:

What is the best case for searching binary search tree? ›

Best case is O(1). the first element could be the item you are looking for. worst case is O(n) ie in a skewed tree and average case is O(lg n).

What is binary search tree with example? ›

A Binary Search Tree (BST) is a type of Binary Tree data structure, where the following properties must be true for any node "X" in the tree: The X node's left child and all of its descendants (children, children's children, and so on) have lower values than X's value.

How does binary search tree work? ›

Definition. A binary search tree (BST) is a binary tree where each node has a Comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node's left subtree and smaller than the keys in all nodes in that node's right subtree.

How do I run a binary search? ›

Below is the Algorithm designed for Binary Search:
  1. Start.
  2. Take input array and Target.
  3. Initialise start = 0 and end = (array size -1)
  4. Intialise mid variable.
  5. mid = (start+end)/2.
  6. if array[ mid ] == target then return mid.
  7. if array[ mid ] < target then start = mid+1.
  8. if array[ mid ] > target then end = mid-1.
Mar 5, 2024

How do you do a binary search? ›

Start by setting the counter to the middle position in the list. If the value held there is a match, the search ends. If the value at the midpoint is less than the value to be found, the list is divided in half, the lower half of the list is ignored and the search keeps to the upper half of the list.

Top Articles
Latest Posts
Recommended Articles
Article information

Author: Stevie Stamm

Last Updated:

Views: 5744

Rating: 5 / 5 (60 voted)

Reviews: 91% of readers found this page helpful

Author information

Name: Stevie Stamm

Birthday: 1996-06-22

Address: Apt. 419 4200 Sipes Estate, East Delmerview, WY 05617

Phone: +342332224300

Job: Future Advertising Analyst

Hobby: Leather crafting, Puzzles, Leather crafting, scrapbook, Urban exploration, Cabaret, Skateboarding

Introduction: My name is Stevie Stamm, I am a colorful, sparkling, splendid, vast, open, hilarious, tender person who loves writing and wants to share my knowledge and understanding with you.