-
Notifications
You must be signed in to change notification settings - Fork 3
/
bst_search.c
99 lines (90 loc) · 2.09 KB
/
bst_search.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/* Program to search a node with a given key in a binary search tree(BST).
*
* Input: 50 30 20 40 70 60 80
* Output: Inorder traversal of the tree is: 20 30 40 50 60 70 80
* Searched node 40 is found
*/
#include <stdio.h>
#include <stdlib.h>
struct node
{
int key;
struct node *left;
struct node *right;
};
// function to create new Binary search tree node
struct node* newNode(int item)
{
struct node* temp = (struct node *) malloc(sizeof(struct node));
temp -> key = item;
temp -> left = temp -> right = NULL;
return temp;
}
// function for inorder traversal of binary search tree
void inorder(struct node* root)
{
if(root != NULL)
{
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}
// function to insert new node with given key in binary search tree
struct node* insert(struct node* node, int key)
{
//if tree is empty, return new node
if(node == NULL)
{
return newNode(key);
}
if(key < node->key)
{
node->left = insert(node->left, key);
}
else if(key > node->key)
{
node->right = insert(node->right, key);
}
return node;
}
// function for searching a node with a given key in BST
struct node* search(struct node* root, int key)
{
// base case: if root is null or key is present at root
if(root == NULL || root->key == key)
{
return root;
}
// if key is smaller than root's key
if(key < root->key)
{
return search(root->left, key);
}
// if key is larger than root's key
return search(root->right, key);
}
int main()
{
struct node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
printf("Inorder traversal of the tree is: ");
inorder(root);
printf("\n");
struct node* temp = search(root, 40);
if(temp)
{
printf("Searched node %d is found\n", temp->key);
}
else
{
printf("Key not found in the BST\n");
}
return 0;
}