Binary search tree is a tree in which the key value of left child is less than the parent node and the key value in right child is greater than the root.
Algorithm to find the node with the given key value:
- Check whether the root node is NULL or not. If it's NULL, there is no tree available. So, return NULL.
- If node T has the search element, then return that node.
- If the search element is less than the key in node T, recursively search the left subtree of T.
- If the search element is greater than the key in node T, recursively search the right subtree of T.
Search for 10.
20
/ \
15 30
/ / \
8 25 40
\
10
TreeNode searchNode(int data, TreeNode T) {
if (!T)
return NULL;
if (data < T->data)
searchNode(data, T->left);
else if (data > T->data)
searchNode(data, T->right);
else if (T->data == data)
return T;
}
Algorithm to find minimum in Binary Search Tree:
The left most node in the left subtree of root node is the minimum element in any given binary search tree.
20
/ \
15 30
/ / \
8 25 40
\
10
int searchMinimum(TreeNode T) {
if (T == NULL)
return NULL;
if (T->left == NULL)
return (T->data);
else
searchMinimum(T->left);
}
Algorithm to find maximum in Binary Search Tree:
The right most node in the right subtree of the root node is the maximum element in any given binary search tree.
20
/ \
15 30
/ / \
8 25 40
\
10
int searchMaximum(TreeNode T) {
if (T == NULL)
return NULL;
if (T->right == NULL)
return (T->data);
else
searchMaximum(T->right);
}
See Also:
C Program To Represent Binary Search Tree Using Arrays
C Program To Perform Insertion, Deletion and Traversal In Binary Search Tree
C Program To Implement Binary Tree Traversals: In-order, Pre-order and Post-order
C Program To Implement Dictionary Using Binary Search Tree
C Program To Perform Searching in Binary Search Tree
C Program To Perform Insertion, Deletion And Traversal In Red Black Tree
C Program To Perform Insertion, Deletion and Traversal in AVL Tree
C Program To Perform Insertion, Deletion and Traversal In B-Tree
C Program To Implement Priority Queue Using Binary Heaps
Construct Binary Search Tree From In-order and Pre-order Traversal Outputs
C Program For Searching In Binary Search Tree(find, findmin and findmax):
#include <stdlib.h>
struct treeNode {
int data;
struct treeNode *left, *right;
};
struct treeNode *root = NULL;
/* create New node */
struct treeNode* createNode(int data) {
struct treeNode *node;
node = (struct treeNode *)malloc(sizeof (struct treeNode));
node->data = data;
node->left = node->right = NULL;
return node;
}
/* insert new node into the binary search tree */
void insert(struct treeNode **myNode, int data) {
if (*myNode == NULL) {
*myNode = createNode(data);
} else if (data < (*myNode)->data) {
insert(&(*myNode)->left, data);
} else if (data > (*myNode)->data) {
insert(&(*myNode)->right, data);
}
}
/* Find the given key value in Binary Search Tree */
void searchAnElement(struct treeNode *myNode, int data) {
if (myNode == NULL) {
printf("Element not found in ur tree\n");
} else if (data < myNode->data) {
searchAnElement(myNode->left, data);
} else if (data > myNode->data) {
searchAnElement(myNode->right, data);
} else if (data == myNode->data) {
printf("I am present!!\n");
}
}
/* find the minimum from our binary search tree */
void findMin(struct treeNode *myNode) {
if (myNode == NULL) {
printf("Tree not Exists\n");
} else if (myNode->left == NULL) {
printf("Min element in tree:%d\n",
myNode->data);
} else {
findMin(myNode->left);
}
}
/* Find Maximum from Binary search tree */
void findMax(struct treeNode *myNode) {
if (myNode == NULL) {
printf("Tree Not Exists\n");
} else if (myNode->right == NULL) {
printf("Max element in tree: %d\n",
myNode->data);
} else {
findMax(myNode->right);
}
}
int main() {
int data, ch;
while (1) {
printf("1. Insertion in Binary Search Tree\n");
printf("2. Find Minimum\n3. Find Maximum\n");
printf("4. Search for an element\n5. Exit\n");
printf("Enter your choice:");
scanf("%d", &ch);
switch (ch) {
case 1:
while (1) {
printf("Enter ur data to insert:");
scanf("%d", &data);
insert(&root, data);
printf("Do you wanna continue insertion(1/0):");
scanf("%d", &ch);
if (ch == 0)
break;
}
break;
case 2:
findMin(root);
break;
case 3:
findMax(root);
break;
case 4:
printf("Enter data to search:");
scanf("%d", &data);
searchAnElement(root, data);
break;
case 5:
exit(0);
break;
case 6:
printf("root->data: %d\n", root->data);
break;
default:
printf("Please enter correct option\n");
break;
}
}
}
Input Tree:
20
/ \
15 30
/ / \
8 25 40
\
10
Output: (C Program To Search Minimum, Maximum & Given Key In BST Tree)
jp@jp-VirtualBox:$ ./a.out
1. Insertion in Binary Search Tree
2. Find Minimum
3. Find Maximum
4. Search for an element
5. Exit
Enter your choice:1
Enter ur data to insert:20
Do you wanna continue insertion(1/0):1
Enter ur data to insert:15
Do you wanna continue insertion(1/0):1
Enter ur data to insert:8
Do you wanna continue insertion(1/0):1
Enter ur data to insert:10
Do you wanna continue insertion(1/0):1
Enter ur data to insert:30
Do you wanna continue insertion(1/0):1
Enter ur data to insert:25
Do you wanna continue insertion(1/0):1
Enter ur data to insert:40
Do you wanna continue insertion(1/0):0
1. Insertion in Binary Search Tree
2. Find Minimum
3. Find Maximum
4. Search for an element
5. Exit
Enter your choice:2
Min element in tree:8
1. Insertion in Binary Search Tree
2. Find Minimum
3. Find Maximum
4. Search for an element
5. Exit
Enter your choice:3
Max element in tree: 40
1. Insertion in Binary Search Tree
2. Find Minimum
3. Find Maximum
4. Search for an element
5. Exit
Enter your choice:4
Enter data to search:10
I am present!!
1. Insertion in Binary Search Tree
2. Find Minimum
3. Find Maximum
4. Search for an element
5. Exit
Enter your choice:5
1. Insertion in Binary Search Tree
2. Find Minimum
3. Find Maximum
4. Search for an element
5. Exit
Enter your choice:1
Enter ur data to insert:20
Do you wanna continue insertion(1/0):1
Enter ur data to insert:15
Do you wanna continue insertion(1/0):1
Enter ur data to insert:8
Do you wanna continue insertion(1/0):1
Enter ur data to insert:10
Do you wanna continue insertion(1/0):1
Enter ur data to insert:30
Do you wanna continue insertion(1/0):1
Enter ur data to insert:25
Do you wanna continue insertion(1/0):1
Enter ur data to insert:40
Do you wanna continue insertion(1/0):0
1. Insertion in Binary Search Tree
2. Find Minimum
3. Find Maximum
4. Search for an element
5. Exit
Enter your choice:2
Min element in tree:8
1. Insertion in Binary Search Tree
2. Find Minimum
3. Find Maximum
4. Search for an element
5. Exit
Enter your choice:3
Max element in tree: 40
1. Insertion in Binary Search Tree
2. Find Minimum
3. Find Maximum
4. Search for an element
5. Exit
Enter your choice:4
Enter data to search:10
I am present!!
1. Insertion in Binary Search Tree
2. Find Minimum
3. Find Maximum
4. Search for an element
5. Exit
Enter your choice:5
No comments:
Post a Comment