binary_search_tree.c
trees Implementation
101 lines2038 bytesC
1// Binary Search Tree (BST)
2#include <stdio.h>
3#include <stdlib.h>
4
5struct Node {
6 int data;
7 struct Node* left;
8 struct Node* right;
9};
10
11struct Node* createNode(int data) {
12 struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
13 newNode->data = data;
14 newNode->left = NULL;
15 newNode->right = NULL;
16 return newNode;
17}
18
19struct Node* insert(struct Node* root, int data) {
20 if (root == NULL) {
21 return createNode(data);
22 }
23
24 if (data < root->data) {
25 root->left = insert(root->left, data);
26 } else if (data > root->data) {
27 root->right = insert(root->right, data);
28 }
29
30 return root;
31}
32
33struct Node* search(struct Node* root, int key) {
34 if (root == NULL || root->data == key) {
35 return root;
36 }
37
38 if (key < root->data) {
39 return search(root->left, key);
40 }
41
42 return search(root->right, key);
43}
44
45void inorder(struct Node* root) {
46 if (root != NULL) {
47 inorder(root->left);
48 printf("%d ", root->data);
49 inorder(root->right);
50 }
51}
52
53void preorder(struct Node* root) {
54 if (root != NULL) {
55 printf("%d ", root->data);
56 preorder(root->left);
57 preorder(root->right);
58 }
59}
60
61void postorder(struct Node* root) {
62 if (root != NULL) {
63 postorder(root->left);
64 postorder(root->right);
65 printf("%d ", root->data);
66 }
67}
68
69int main() {
70 struct Node* root = NULL;
71
72 root = insert(root, 50);
73 insert(root, 30);
74 insert(root, 20);
75 insert(root, 40);
76 insert(root, 70);
77 insert(root, 60);
78 insert(root, 80);
79
80 printf("Inorder traversal: ");
81 inorder(root);
82 printf("\n");
83
84 printf("Preorder traversal: ");
85 preorder(root);
86 printf("\n");
87
88 printf("Postorder traversal: ");
89 postorder(root);
90 printf("\n");
91
92 struct Node* found = search(root, 40);
93 if (found != NULL) {
94 printf("Found: %d\n", found->data);
95 } else {
96 printf("Not found\n");
97 }
98
99 return 0;
100}
101