Binary Search Tree in data structure is type of tree in data structure.
In this tutorial we will see what is binary search tree, binary search tree definition, program for binary search tree.
Binary search tree definition
Binary search tree (BST) is a binary tree in which each node has value greater than every node of left subtree and less than every node of right subtree.
It is very useful data structure in which item can be searched in O(log N) where N is number of nodes.
Binary search tree complexity : O(log N)
Insertion operation on Binary search tree
- compare data with data of root node.
- If data < data of node then compare with data of left child node and insert it to proper place.
- if data > data of node then compare with data of right child node and insert it to proper place.
Deletion operation on Binary search tree
- In deletion if the deleting node is leaf node then simply delete node.
- If the node which is deleting has some child then after deleting the node adjust its child according to the Binary search tree properly.
Binary Search Tree Traversal
Preorder traversal
- Visit the root
- Traverse the left subtree of root.
- traverse right subtree of root
Inorder traversal
- Traverse left subtree of root
- visit root
- traverse right subtree of root
Postorder traversal
- traverse left subtree of root.
- traverse right subtree of root
- visit root
Tree traversal example

Consider above tree with A,B,D,E,F,G nodes of tree.
Lets traverse the tree using tree traversal methods in data structure.
Preorder traversal = A B E G D F
Inorder traversal = E B G A F D
Postorder traversal = E G B F D A
Program to implement binary search tree in data structure
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 |
#include<stdio.h> #include<stdlib.h> struct node { int data; struct node* left; struct node* right; }; struct node* createNode(value){ struct node* newNode = malloc(sizeof(struct node)); newNode->data = value; newNode->left = NULL; newNode->right = NULL; return newNode; } struct node* insert(struct node* root, int data) { if (root == NULL) return createNode(data); if (data < root->data) root->left = insert(root->left, data); else if (data > root->data) root->right = insert(root->right, data); return root; } void inorder(struct node* root){ if(root == NULL) return; inorder(root->left); printf("%d ->", root->data); inorder(root->right); } int main(){ struct node *root = NULL; root = insert(root, 8); insert(root, 3); insert(root, 1); insert(root, 6); insert(root, 7); insert(root, 10); insert(root, 14); insert(root, 4); printf("Binary search tree\n"); inorder(root); } |
Output:

Leave a Reply