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

/* 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:

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

Ref: Wikipedia.org




Related Contents to follow