Binary Search Tree (BST) is a Binary Tree with the constraint:
the value stored at the root of a sub-tree is greater than or equal to any value in its left sub-tree and less than any value in its right sub-tree.
In a Binary Search Tree (BST):
- The smallest element in Binary Search Tree can be found at the leftmost node.
- The largest element in Binary Search Tree can be found at the rightmost node.
- To search for an element in BST, compare it with root node, if it is ≥ the root, it will be found in left sub-tree (if available), otherwise will be found in right sub-tree.

Fig. 1: Binary Search Tree example

Fig. 2: Binary Search Tree example
#include<stdio.h> #include<stdlib.h> //This structure will store the contents of a node ([left child pointer | Data | right child pointer]). //Both the pointers will have to point another node so, they has to be of type node. //If we want to store the address of an int we used to declare the point as int *p, similarly, //here we want to store the address of child nodes (represented by our structure BST) that's why, //struct BST *lchild, *rchild //typedef is used so that we can use "node" variable name for our structure instead of "struct BST" typedef struct BST { int data; struct BST *lchild, *rchild; } node; // "insert" function is written to add a new element to the BST. Two arguments are passed into this, first one is //the address of root node of the BST and second is address of the newly created node, to be inserted. void insert(node *, node *); //"inorder" function is written to display the tree with in-order traversal. The argument passed is the address of //the root node. void inorder(node *); //"preorder" function is written to display the tree with pre-order traversal. The argument passed is the address //of the root node. void preorder(node *); //"postorder" function is written to display the tree with post-order traversal. The argument passed is the address //of the root node. void postorder(node *); //"get_node" function is written to create a new node and return the address of the newly created node node *get_node(); int main() { int choice; // this variable is used to select the display method of the tree char ans = 'N'; //to ask user whether to insert more nodes. Default is "N" and will continue for "y" //new_node is to store the address of newly created node, root is store the address of root node (required //as the starting point of the tree. (Same as start pointer in a link list). node *new_node, *root, *tmp; root = NULL; //initializing the root to be NULL printf("\nProgram For Binary Search Tree "); do { new_node = get_node(); // a node is created printf("\nEnter The Element "); scanf("%d", &new_node->data); // data of the node if (root == NULL) // The tree is empty (no root node) root = new_node; // created node is treated as root ode and used for futur to start with else //root node is created, call insert to add newly created node to tree, passing the address of //root node to (starting point of the link list/tree) and the address of newly created node insert(root, new_node); printf("\nWant To enter More Elements?(y/n)"); scanf("%s",&ans); } while (ans == 'y'); if (root == NULL) printf("Tree Is Not Created"); else { printf("\nThe Inorder display : "); inorder(root); //the address of root is passed so start with (start of link list) printf("\nThe Preorder display : "); preorder(root); printf("\nThe Postorder display : "); postorder(root); } return 0; } /* Get new Node */ node *get_node() { node *temp; temp = (node *) malloc(sizeof(node)); //memory is created of size node and address of it is returned temp->lchild = NULL; //both the child nodes are pointing to NULL (no children are created for it till now). temp->rchild = NULL; return temp; // return the address of newly created node } /* This function is for creating a binary search tree */ void insert(node *root, node *new_node) { //to check whether the node has to be inserted in left or right side if (new_node->data < root->data) { //if new nodes data is < the root node data, add to the left side if (root->lchild == NULL) //if no left child is created till now root->lchild = new_node; //add the new node as left child else insert(root->lchild, new_node); //otherwise, assume the left child as root node and insert new node to this sub-tree } if (new_node->data > root->data) {//if new nodes data is > the root node data, add to the right side if (root->rchild == NULL) //if no right child is created till now root->rchild = new_node; //add the new node as right child else insert(root->rchild, new_node); //otherwise, assume the right child as root node and insert new node to this sub-tree } } /* This function displays the tree in inorder fashion */ void inorder(node *temp) { //temp is the address of root of the tree if (temp != NULL) { //to check that tree is not empty inorder(temp->lchild); //traverse the left sub-tree first recursively, until the NULL is found printf("%d", temp->data); // print the data inorder(temp->rchild); //traverse the right sub-tree recursively } } /* This function displays the tree in preorder fashion */ void preorder(node *temp) { if (temp != NULL) { printf("%d", temp->data); preorder(temp->lchild); preorder(temp->rchild); } } /* This function displays the tree in postorder fashion */ void postorder(node *temp) { if (temp != NULL) { postorder(temp->lchild); postorder(temp->rchild); printf("%d", temp->data); } }
Coming soon.