A binary search tree where the left child contains only nodes with values less than the parent node, and where the right child only contains nodes with values greater than or equal to the parent node, is called Binary search tree. Also both left and right subtrees are binary search trees themselves.

There are three types of traversal explained here with example code:

• In order traversal
• Pre order traversal
• Post order traversal

```/* binary search tree */

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
struct Node *left; /* left child */
int data; /* data to be stored*/
struct Node *right; /* right child */
}Node;

Node* insert(Node * node, int a);
void In_order_traverse(Node * node);
void Pre_order_traverse(Node* node);
void Post_order_traverse(Node * node);

int main() {

Node *root = NULL; /* root of binary tree */
root = insert(root, 5);
insert(root, 3);
insert(root, 6);
insert(root, 4);

/* in order traverse*/
In_order_traverse(root);
printf("\n");

/* pre order */
Pre_order_traverse(root);
printf("\n");

/* post order */
Post_order_traverse(root);
printf("\n");

return 0;
}

Node* insert(Node* node, int a) {
/* create first node */
if (node == NULL) {
Node* tmp = (Node*) malloc(sizeof(Node));
tmp->left = NULL;
tmp->right = NULL;
tmp->data = a; // initialize with zero
return tmp;
}

if (a < node->data) /* go to left */
node->left = insert(node->left, a);
else
// go to right
node->right = insert(node->right, a);
return node;
}

void In_order_traverse(Node *node) {
if (node != NULL) {
In_order_traverse(node->left);
printf("%d ", node->data);
In_order_traverse(node->right);
}
}

void Pre_order_traverse(Node* node) {
if (node != NULL) {
printf("%d ", node->data);
Pre_order_traverse(node->left);
Pre_order_traverse(node->right);
}

}
void Post_order_traverse(Node* node) {
if (node != NULL) {
Post_order_traverse(node->left);
Post_order_traverse(node->right);
printf("%d ", node->data);
}

}
```

Time complexity:

Space Search Insert Average Worst case O(n) O(n) O(log n) O(n) O(log n) O(n) O(log n) O(n)

Ref: Wikipedia.org