 # Binary Search Tree – analysis and implementation with c/c++ and JAVA

Ankur Kulhari

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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.