AVL Tree in C language

AVL Tree in C language

Use C programming language to make an AVL tree and display the tree in INORDER formate.

Code

/******AVL tree******/
#include <stdio.h>
#include <stdlib.h>

//Structure for tree
struct AVL 
{
 int data,height;
 struct AVL *left,*right;
};

//Function definition for getting maximum value
int max(int a,int b)
{
 if(a>=b)
  return a;
 else
  return b; 
}

//Function definition for getting the height of the tree
int height(struct AVL **root)
{
 if(*root==NULL)
  return 0;
 return (*root)->height; 
}

//Function definition for getting the balance factor of the tree
int balance(struct AVL **root)
{
 return(height(&((*root)->left))-height(&((*root)->right)));
}

//Function definition for rotate the tree right
void rightrotate(struct AVL **root)
{
 struct AVL *child,*temp;
 child=(*root)->left;
 temp=child->right;
 child->right=*root;
 (*root)->left=temp;
 (*root)->height=max(height(&((*root)->left)),height(&((*root)->right)))+1;
 child->height=max(height(&((*root)->left)),height(&((*root)->right)))+1;
 *root= child;
 
}

//Function definition for rotate the tree left
void leftrotate(struct AVL **root)
{
 struct AVL *child,*temp;
 child=(*root)->right;
 temp=child->left;
 child->left=*root;
 (*root)->right=temp;
 (*root)->height=max(height(&((*root)->left)),height(&((*root)->right)))+1;
 child->height=max(height(&((*root)->left)),height(&((*root)->right)))+1;
  *root=child;
}

//Function definition for creating
void create(struct AVL **root,int d)
{  int bal;
 if(*root==NULL)
 {
   *root=(struct AVL*)malloc(sizeof(struct AVL));
   (*root)->data=d;
   (*root)->height=1;
   (*root)->left=NULL;
   (*root)->right=NULL;
   return; 
 }
 else if(d > (*root)->data)
  create(&((*root)->right),d);
 else if(d < (*root)->data)
  create(&((*root)->left),d);
 else
   printf("item already exist");
 (*root)->height=max(height(&((*root)->left)),height(&((*root)->right)))+1;  
 bal=balance(&(*root));
 if(bal< -1 && d < (*root)->right->data)
 {
  rightrotate(&((*root)->right));
  leftrotate(&(*root));
 }
 if(bal > 1 && d < (*root)->left->data)
  rightrotate(&(*root)); 
 if(bal < -1 && d < (*root)->right->data)
 {
  leftrotate(&(*root));
 }
 if(bal > 1 && d > (*root)->left->data)
 {
  leftrotate(&((*root)->left));
  rightrotate(&(*root));
 }
    
}

//Function definition for inorder traversal
void inorder(struct AVL **root)
{
 if(*root)
 {
  inorder(&((*root)->left));
  printf("%d\t",(*root)->data);
  inorder(&((*root)->right));
 }
}
int main()
{
 struct AVL *root=NULL;
 int ch,d;
 do
 {   
  printf("\n1.create or insert element to AVL tree");
  printf("\n2.inorder display element to tree");
  printf("\n3.exit");
  printf("\nenter ur choice");
  scanf("%d",&ch);
  switch (ch)
  {
   case 1:
    printf("\nenter element to new node");
    scanf("%d",&d);
    create(&root,d);
    break;
   case 2:
    inorder(&root);
    getch();
    break;
   case 3:
    exit(0);
   default:
    printf("invalid choice");   
  }
 }while(1);
 return (0); 
}

Output

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice1

enter element to new node10

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice1

enter element to new node5

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice1

enter element to new node15

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice1

enter element to new node3

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice1

enter element to new node2

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice1

enter element to new node6

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice2
2       3       5       6       10      15

Hashing Using C language

Hashing Using C language

Create a Hash Table in C language and search table elements.

Code

/*****Hashing technique and collision resolution******/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

//Creating structure
struct Hash{
 int info;
 struct Hash *next;
};

//Function declaration
void search(struct Hash *key,int n);
void display(struct Hash *key,int n);
void insert(struct Hash **key,int n);

int main(){
 int n,i,choice;
 struct Hash *key;
 printf("Enter no of key you want to create:\t");
 scanf("%d",&n);
 key=(struct Hash *)calloc(n,sizeof(struct Hash));
 for(i=0;i<n;i++){
 (key+i)->info=i;
 (key+i)->next=NULL;
 }
 display(key,n);
 while(1){
  printf("\nOPTIONS\n");
  printf("1.Insert\n");
  printf("2.Search\n");
  printf("3.Exit\n");
  printf("Enter choice:\t");
  scanf("%d",&choice);
  switch(choice){
    case 1: insert(&key,n);
      display(key,n);
      break;

    case 2: display(key,n);
      search(key,n);
      break;

    case 3: exit(0);
   default: printf("Enter correct option!!!");
  }
 }
}

//Function definition for insert
void insert(struct Hash **key,int n){
  struct Hash *temp;
  int formulae,element;
   temp=(struct Hash *)calloc(1,sizeof(struct Hash));
   printf("Enter the element:\t");
   scanf("%d",&element);
   temp->info=element;
   temp->next=NULL;
   formulae = element % n;
   if ((*key+formulae)->next==NULL)
   (*key+formulae)->next=temp;
   else{
   temp->next=(*key+formulae)->next;
   (*key+formulae)->next=temp;
   }
}
//Function definition for Display
void display(struct Hash *key,int n){
  int i;
  struct Hash *temp;
  printf("Key\tElements");
 for(i=0;i<n;i++){
  temp=(key+i);
  printf("\n");
  while(temp!=NULL){
   printf("%d\t",(temp)->info);
   temp=temp->next;
  }
 }
}
//Function defination for search
void search(struct Hash *key,int n){
 int search_element,key_index,column=1,i=0;
  struct Hash *temp;
  printf("\nEnter the element to search:\t");
  scanf("%d",&search_element);
  key_index=search_element%n;
  temp=(key+key_index)->next;
 while(temp!=NULL){
  if (temp->info==search_element){
   printf("[%d] is present at [%d] row and [%d] column.",search_element,key_index,column);
   i=1;
  }
  temp=temp->next;
  column=column+1;
 }
 if(i==0)
  printf("[%d] is not present in Hash table.",search_element);
}

Output

Enter no of key you want to create:     5
Key     Elements
0
1
2
3
4
OPTIONS
1.Insert
2.Search
3.Exit
Enter choice:   1
Enter the element:      10
Key     Elements
0       10
1
2
3
4
OPTIONS
1.Insert
2.Search
3.Exit
Enter choice:   1
Enter the element:      54
Key     Elements
0       10
1
2
3
4       54
OPTIONS
1.Insert
2.Search
3.Exit
Enter choice:   1
Enter the element:      69
Key     Elements
0       10
1
2
3
4       69      54
OPTIONS
1.Insert
2.Search
3.Exit
Enter choice:   1
Enter the element:      87
Key     Elements
0       10
1
2       87
3
4       69      54
OPTIONS
1.Insert
2.Search
3.Exit
Enter choice:   1
Enter the element:      21
Key     Elements
0       10
1       21
2       87
3
4       69      54
OPTIONS
1.Insert
2.Search
3.Exit
Enter choice:   2
Key     Elements
0       10
1       21
2       87
3
4       69      54
Enter the element to search:    54
[54] is present at [4] row and [2] column.
OPTIONS
1.Insert
2.Search
3.Exit
Enter choice:   2
Key     Elements
0       10
1       21
2       87
3
4       69      54
Enter the element to search:    21
[21] is present at [1] row and [1] column.
OPTIONS
1.Insert
2.Search
3.Exit
Enter choice:   2
Key     Elements
0       10
1       21
2       87
3
4       69      54
Enter the element to search:    58
[58] is not present in Hash table.
OPTIONS
1.Insert
2.Search
3.Exit
Enter choice:   3

Read A Text File Using C

Read a text file using C

Open a text file using C program and read the content of the file.

Code

/*Write a program to read a file*/
#include <stdio.h>
#include <stdlib.h>

int main()
{
 FILE *fp; //Taking a file pointer variable
 char fname[30],ch;

 //Taking a existing file name from the user to read
 printf("\nEnter a file name to read: ");
 gets(fname);

 //Open the file in read mode
 fp=fopen(fname,"r");
 
 //Check the file is corrupted or not
 if(fp==NULL)
 {
  printf("\nFile cannot be access.");
  exit(0);
 }
 if(ferror(fp)!=0)
 {
  printf("\nFile is either corrupted or damaged");
  exit(1);
 }

 //Print the content of the file
 while((ch=getc(fp))!=EOF)
 {
  printf("%c",ch);
 }

 //Close the file
 fclose(fp);

 return 0;
}

Output>

Enter a file name to read: temp.txt
This is a temporary file.

Note:

To read a file you have to create a file first by using any text editor(Notepad) or you can also use the C program to create a file.

C Program to Store Record In A File

C program to store students records in a file

The main purpose of this program is that to store some information in a file from console.

Code

/*Write a program that will read roll, name and marks of several student from the user and store them in a file*/
#include <stdio.h>
#include <stdlib.h>
//Create a structure for store the records for all students
struct student
{
 int roll;
 char name[30];
 int marks;
} s;
int main( ){
 FILE *fp; //Create a file pointer variable
 char fname[20],s2[20];
 int n,i,s1,s3;
 printf("\nEnter a file name to store student record: ");
 gets(fname);
 //Open the file in write mode
 fp=fopen(fname,"w");
 if(fp==NULL){
  printf("\nError:FIle cannot be created. \a");
  exit(0);
 }
 printf("\nEnter the number of student: ");
 scanf("%d",&n);
 //Taking the records of students and store them in the file
 for(i=0;i<n;i++){
  printf("\nFor student no. %d", i+1);
  printf("\nEnter roll: ");
  scanf("%d",&s.roll);
  printf("\nEnter name: ");
  scanf("%s",&s.name);
  printf("\nEnter marks: ");
  scanf("%d",&s.marks);
  fprintf(fp,"%d\t%s\t%d\n",s.roll,s.name,s.marks);
 }
 //Close the file
 fclose(fp);
 //Open the file in read mode
 fp=fopen(fname,"r");
 if(fp==NULL){
  printf("\nError:FIle does not exist. \a");
  exit(0);
 }
 if(ferror(fp)!=0){
  printf("\nError: File is either corrupted or damaged. \a");
  exit(0);
 }

 //Print the content of the file
 for(i=1;i<=n;i++){
  fscanf(fp,"%d\t%s\t%d\n",&s1,&s2,&s3);
  printf("\n%d\t%s\t%d",s1,s2,s3);
 }
 //Close the file
 fclose(fp);
 return(0);
}

Output

Enter a file name to store student record: student.txt
Enter the number of student: 3
For student no. 1
Enter roll: 101
Enter name: Alex
Enter marks: 85
For student no. 2
Enter roll: 102
Enter name: Rose
Enter marks: 96
For student no. 3
Enter roll: 103
Enter name: Charls
Enter marks: 93
The content of the file is:
101     Alex    85
102     Rose    96
103     Charls  93

C Program to Count From A File

C program to count from a file

Count the numbers of characters, vowels, consonant, lines, words, punctuation marks from a existing file.

Code

/*Write a program that will read the contains of a file and count the characters, vowels, consonant, lines, words, punctuation marks */
#include <stdio.h>
#include <stdlib.h>

int main()
{
 FILE *fp;
 char fname[30],ch;
 int c=0,v=0,ln=0,w=0,p=0;

 //Taking a file name from the user
 printf("\nEnter a file name to read: ");
 gets(fname);

 //Open the file in read mode
 fp=fopen(fname,"r");
 
 //Check is the file exist or not
 if(fp==NULL)
 {
  printf("\nFile cannot be access.");
  exit(0);
 }

 //Print the content of the file
 printf("\nThe contain of the file is: \n");
 while((ch=getc(fp))!=EOF)
 {
  printf("%c",ch);
  
  //Checking and count the outputs
  if((ch>=65&&ch<=90)||(ch>=97&&ch<=122))
  {
   c=c+1;
  }
  if((ch=='a')||(ch=='e')||(ch=='i')||(ch=='o')||(ch=='u')||(ch=='A')||(ch=='E')||(ch=='I')||(ch=='O')||(ch=='U'))
  {
   v=v+1;
  }
  if((ch=='.')||(ch=='?')||(ch=='!'))
  {
   ln=ln+1;
   w=w+1;
  }
  if(ch==' ')
  {
   w=w+1;
  }
  if((ch==';')||(ch=='"')||(ch==','))
  {
   p=p+1;
  }
 }
 //Print the outputs
 printf("\nNumber of character in the file is %d",c);  //Count the characters
 printf("\nNumbers of vowels in the file is %d",v);               //Count the vowels
 printf("\nNumbers of consonant in the file is %d",(c-v));       //Count the consonants
 printf("\nNumbers of lines in the file is %d",ln);              //Count the lines
 printf("\nNumbers of words in the file is %d",w);               //Count the words
 printf("\nNumbers of punctuation marks in the file is %d",p);   //Count the punctuation marks
 fclose(fp);

 return 0;
}

Output

Enter a file name to read: temp.txt

The containt of the file is:
This is a temporary file.

Number of charecter in the file is 20
Numbers of vouls in the file is 8
Numbers of consonent in the file is 12
Numbers of lines in the file is 1
Numbers of words in the file is 5
Numbers of punchuation marks in the file is 0

Find Minimum In Stack In O(1) Time and O(1) Space

Find Minimum In Stack In O(1) Time and O(1) Space

For this problem I have used a stack of pointer to nodes. A node have two members one is the value part and another is the link to another node.

Conditions

• Update the minimum with each push operation
• A node (current) will point to another node if the current node have a previous minimum node else it will point to null
• During pop check the top node and the minimum node if they point to the same location then update the current minimum to previous minimum by assigning the link of the top node to minimum pointer
• If the top node has null to its link part then it is not the minimum node and no pointer manipulation needed,

Sample Operations

C++ Implementation

#include <iostream>
using namespace std;
#define MAX 9999

struct Node {
    int val;
    struct Node *add;
};

class Stack
{
    Node **arr, *minn;
    int s, top;

    public:
        Stack(int s) : s(s) {
            arr = new Node*[s];
            top = -1;
            minn = new Node();
            minn->val = MAX;
        }
        ~Stack() {
            delete [] arr;
        }

        void push(int item);
        int pop();
        int minimum() const {
            return (top ==-1)? -1 : minn->val;
        };
};

void Stack::push(int item) {
    if (top == s-1) {
        cout << "Stack full!" << endl;
    }
    else {
        Node *tmp = new Node();
        tmp->add = NULL;
        if (top == -1) {
            minn = tmp;
        }
        else {
            if (item <= minn->val) {
                tmp->add = minn;
                minn = tmp;
            }
        }
        tmp->val = item; ++top;
        arr[top] = tmp;
    }
}

int Stack::pop()
{
    int retVal = -1;
    if (top == -1) {
        delete minn;
        cout << "Stack empty!" << endl;
    }
    else {
        retVal = arr[top]->val;
        if (arr[top] == minn){
            minn = arr[top]->add;
        }
        top--;
    }
    return retVal;
}

int main()
{
    Stack s(6);
    s.push(7);
    s.push(1);
    s.push(1);
    s.push(2);
    s.push(4);
    s.push(0);
    cout << "Current Min: " << s.minimum() << endl;
    cout << "Popped: " << s.pop() << endl;
    cout << "Current Min: " << s.minimum() << endl;
    cout << "Popped: " << s.pop() << endl;
    cout << "Current Min: " << s.minimum() << endl;
    cout << "Popped: " << s.pop() << endl;
    cout << "Current Min: " << s.minimum() << endl;
    cout << "Popped: " << s.pop() << endl;
    cout << "Current Min: " << s.minimum() << endl;
    cout << "Popped: " << s.pop() << endl;
    cout << "Current Min: " << s.minimum() << endl;
    cout << "Popped: " << s.pop() << endl;
    return 0;
}

Current Min: 0
Popped: 0
Current Min: 1
Popped: 4
Current Min: 1
Popped: 2
Current Min: 1
Popped: 1
Current Min: 1
Popped: 1
Current Min: 7
Popped: 7

Process returned 0 (0x0)   execution time : 0.044 s
Press any key to continue.

If you find anything wrong please comment below. And if you have any other approach then mail me at itsaboutcs@gmail.com.

C Program To Reverse A Linked List

C Program Reverse A Linked List

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

struct Node
{
    int data;
    struct Node *next;
};


struct Node* createList(struct Node *head, int n)
{
    int i, item;
    struct Node *nw, *temp;
    for(i = 0; i < n; i++)
    {
        nw = (struct Node*)malloc(sizeof(struct Node));
        nw->next = NULL;
        printf("Enter Data: ");
        scanf("%d", &item);
        nw->data = item;
        if (i == 0)
        {
            head = nw;
            temp = head;
        }
        else
        {
            temp->next = nw;
            temp = temp->next;
        }
    }
    return head;
}

void disp(struct Node *head)
{
    struct Node *temp = head;
    while(temp != NULL)
    {
        printf("%d ",temp->data);
        temp = temp->next;
    }
}

struct Node* reverse(struct Node *head)
{
    struct Node *prev = NULL, *next = NULL;
    struct Node *curr = head;

    while(curr != NULL)
    {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;
    return head;
}

int main()
{
    struct Node *head = NULL;
    head = createList(head, 5);
    disp(head);
    head = reverse(head);
    printf("\n");
    disp(head);
    return 0;
}

Enter Data: 5
Enter Data: 4
Enter Data: 3
Enter Data: 2
Enter Data: 1
5 4 3 2 1
1 2 3 4 5
--------------------------------
Process exited after 4.487 seconds with return value 0
Press any key to continue . . .

Binary Search Tree | Deletion

Deletion of a node in a BST can be more complicated task than searching or inserting a node.

Suppose we want to delete a node P

1> If P is a leaf node i.e. it has no children, then we will just replace P by null.

          8                               8
        /   \          delete(9)        /   \
       3    10         ---------->     3    10
      / \   /                         / \
     1   5 9                         1   5

2> If P has only one child, then we will place the child to P's place.

          8                               8
        /   \          delete(10)       /   \
       3    10         ---------->     3     9
      / \   /                         / \
     1   5 9                         1   5

3>If P has two children, then we will identify P's successor. Call it Q. The successor Q either is a leaf or has only the right child. We will replace P by Q and delete Q.(if it has right child then follow method 2)

         8                              9
       /   \          delete(8)       /   \
      3    10         ---------->    3    10
     / \   /                        / \
    1   5 9                        1   5

C Program

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

typedef struct BST
{
   struct BST *lc, *rc;
   int data;
}BST;

BST *insertNode(BST *T,int item)
{
    BST *curr = T,*prev = NULL,*temp = NULL;
    int found = 0;
    //Search for the proper position of the node to insert...
    while(curr != NULL && !found)
    {
        //Keeping track of the previous node...
        prev = curr; 
        // If item already exists...
        if(curr->data == item) 
        {
            found = 1;
            printf("\nItem %d Already Exists In The BST.\n",item);
        }
        else if(curr->data > item) {
            curr = curr->lc;
        }
        else {
            curr = curr->rc;
        }
    }
    //Creating a new node...
    temp = (BST*)malloc(sizeof(BST));
    temp->data = item;
    temp->lc = NULL;
    temp->rc = NULL;
    //Only for first node or time...
    if(T == NULL)
        T = temp;
    else if(item > prev->data)
        prev->rc = temp;
    else
        prev->lc = temp;
    return T;
}

void inorder(BST *t)
{
    if(t != NULL) 
    {
        inorder(t->lc);
        printf("%d ",t->data);
        inorder(t->rc);
    }
}

BST *deleteNode(BST *root,int item)
{
    BST *curr = root, *temp = NULL, *parent;
    while(curr != NULL)
    {
        if(curr->data == item)
            break;
        parent  = curr;
        if(item > curr->data)
            curr = curr->rc;
        else
            curr = curr->lc;
    }
    if(curr == NULL)
    {
        printf("\nDelete Request Failed. Value Not Exists.");
        return root;
    }
    else if(curr->lc == NULL && curr->rc == NULL) // Leaf node (case 1)
    {
        if(parent == NULL)
            root = NULL;
        else if(parent->lc == curr)
            parent->lc = NULL;
        else
            parent->rc = NULL;
        return root;
    }
    else if(curr->lc != NULL && curr->rc == NULL) // Only one child (case 2)
    {
        if (root->data == curr->data) 
            root = curr->lc;
        else if(parent->lc == curr)
            parent->lc = curr->lc;
        else
            parent->rc = curr->lc;
        free(curr);
        return root;
    }
    else if(curr->rc != NULL && curr->lc == NULL) // Only one child (case 2)
    {
        if (root->data == curr->data) 
            root = curr->rc;
        else if(parent->lc == curr)
            parent->lc = curr->rc;
        else
            parent->rc = curr->rc;
        free(curr);
        return root;
    }
    else // both child (case 3)
    {
        parent = curr;
        temp = curr->rc;
        while(temp->lc != NULL)
        {
            parent = temp;
            temp = temp->lc;
        }
        curr->data = temp->data;
        if(curr == parent)
            curr->rc = temp->rc;
        else
            parent->lc = temp->rc;      
        free(temp);
        return root;
    }
}

int main()
{
    BST *T = NULL;
    int value;
    T = insertNode(T, 8);
    insertNode(T, 3);
    insertNode(T, 10);
    insertNode(T, 1);
    insertNode(T, 5);
    insertNode(T, 9);
    
    printf("Full Tree: ");
    inorder(T);
    printf("\nAFter Deleting 9(leaf node): ");
    T = deleteNode(T, 9);
    inorder(T);
    printf("\nAFter Deleting 10(node w/ one child): ");
    T = deleteNode(T, 10);
    inorder(T);
    printf("\nAFter Deleting 8(root node): ");
    T = deleteNode(T, 8);
    inorder(T);
    printf("\nAFter Deleting 3(full node): ");
    T = deleteNode(T, 3);
    inorder(T);
    return 0;
}

Output

Full Tree: 1 3 5 8 9 10
AFter Deleting 9(leaf node): 1 3 5 8 10
AFter Deleting 10(node w/ one child): 1 3 5 8
AFter Deleting 8(root node): 1 3 5
AFter Deleting 3(full node): 1 5
--------------------------------
Process exited after 0.4866 seconds with return value 0
Press any key to continue . . .

Binary Search Tree | Searching

We assume that a key and the subtree in which the key is searched for are given as an input. We'll take the full advantage of the BST-property.

Suppose we are at a node. If the node has the key that is being searched for, then the search is over. Otherwise, the key at the current node is either strictly smaller than the key that is searched for or strictly greater than the key that is searched for. If the former is the case, then by the BST property, all the keys in th left subtree are strictly less than the key that is searched for. That means that we do not need to search in the left subtree. Thus, we will examine only the right subtree. If the latter is the case, by symmetry we will examine only the right subtree.

Searching | Best Case

It takes O(lg(n)) time to search in this tree. as the hight is lg(n).

        5
       / \
      1   6
     / \
    0   2

Searching | Wrost Case

It takes O(n) time to search in this tree. as the hight is n.

        5
       / 
      4   
     / 
    3 
   / 
  2

C Program

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

typedef struct BST
{
   struct BST *lc, *rc;
   int data;
}BST;

void inorder(BST *t)
{
    if(t != NULL) {
        inorder(t->lc);
        printf("%d ",t->data);
        inorder(t->rc);
    }
}

BST *insertNode(BST *T,int item)
{
    BST *curr = T,*prev = NULL,*temp = NULL;
    int found = 0;
    //Search for the proper position of the node to insert...
    while(curr != NULL && !found)
    {
        //Keeping track of the previous node...
        prev = curr; 
        // If item already exists...
        if(curr->data == item) 
        {
            found = 1;
            printf("\nItem %d Already Exists In The BST.\n",item);
        }
        else if(curr->data > item) {
            curr = curr->lc;
        }
        else {
            curr = curr->rc;
        }
    }
    //Creating a new node...
    temp = (BST*)malloc(sizeof(BST));
    temp->data = item;
    temp->lc = NULL;
    temp->rc = NULL;
    //Only for first node or time...
    if(T == NULL)
        T = temp;
    else if(item > prev->data)
        prev->rc = temp;
    else
        prev->lc = temp;
    return T;
}

short searchNode(BST *T, int item)
{
 BST *curr = T,*prev = NULL,*temp = NULL;
    int found = 0;
    //Search for the proper position of the node to insert...
    while(curr != NULL && !found)
    {
        // If item already exists...
        if(curr->data == item) {
         return 1;
        }
        else if(curr->data > item) {
            curr = curr->lc;
        }
        else {
            curr = curr->rc;
        }
    }
    return 0;
}
int main()
{
    BST *T = NULL;
    int value;
    
    printf("Enter VAlues In BST:\n");
    scanf("%d",&value);
    while (value != -999) {
        T = insertNode(T, value);
        scanf("%d",&value);
    }
    
    inorder(T);

    printf("\nEnter A Search Value: ");
    scanf("%d",&value);
    printf("%d Is %sOn The Tree.\n",value,searchNode(T, value)?"":"Not ");
    
    printf("\nEnter Another Search Value: ");
    scanf("%d",&value);
    printf("%d Is %sOn The Tree.\n",value,searchNode(T, value)?"":"Not ");
    return 0;
}

Output

Enter VAlues In BST:
3 2 1 4 5 6 -999
1 2 3 4 5 6
Enter A Search Value: 5
5 Is On The Tree.

Enter Another Search Value: 7
7 Is Not On The Tree.

Binary Search Tree | Insertion

Binary Search Tree (BST) is node based binary tree data structure with the following properties:

• The Left subtree contains the nodes with keys less than the node's key.
• The Right subtree contains the nodes with keys greater than the node's key.
• Both the right and left subtree should also be binary search tree.
• There should not be any duplicate key.

Inserting a node in binary search tree behaves in the same manner as searching operation. Firstly, it checks whether the key is the same as that of root, if not then we either choose the right subtree or the left subtree depending on the value passed is greater or smaller than the root node value respectively.

Eventually, we will reach an external node where we will add the new node as its left or right child depending upon the node's key.

This is also a recursive operation, as we start from the root and go until we find the right place to insert to node.

Insertion time in a BST is proportional to the height of the tree.

Example

Insert: 5 2 8 1 4 7 9 0 3 6

                (5)

           /           \

         (2)            (8)

       /   \           /   \

    (1)    (4)        (7)  (9)

   /       /       /

 (0)     (3)    (6)

We used this structure with three members to represent each node in the tree. Here data represents the key of the node and lc and rc are pointers to the left and right subtree respectively

typedef struct BST
{
   struct BST *lc, *rc;
   int data;
}BST;

C Program

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

typedef struct BST
{
   struct BST *lc,*rc;
   int data;
}BST;
 
void inOrder(BST *t)
{
    if(t != NULL) {
        inOrder(t->lc);
        printf("%d ",t->data);
        nOrder(t->rc);
    }
}
 
BST *insertNode(BST *T, int item)
{
    BST *curr = T,*prev = NULL,*temp = NULL;
    int found = 0;
    //Search for the proper position of the node to insert...
    while(curr != NULL && !found) {
        //Keeping track of the previous node...
        prev=curr; 
        // If item already exists...
        if(curr->data == item) {
            found = 1;
            printf("\nItem %d Already Exists In The BST.\n",item);
        }
        else if(curr->data > item)
            curr = curr->lc;
        else
            curr = curr->rc;
    }
    //Creating a new node...
    temp = (BST*)malloc(sizeof(BST));
    temp->data = item;
    temp->lc = NULL;
    temp->rc = NULL;
    //Only for first node or time...
    if(T == NULL)
        T = temp;
    else if(item > prev->data)
        prev->rc = temp;
    else
        prev->lc = temp;
    return T;
}
  
int main()
{
    BST *T = NULL;
    T = insertNode(T, 5);
    insertNode(T, 2);
    insertNode(T, 8);
    insertNode(T, 1);
    insertNode(T, 4);
    insertNode(T, 7);
    insertNode(T, 9);
    insertNode(T, 0);
    insertNode(T, 3);
    insertNode(T, 6);
    inOrder(T);
    return 0;
}

Output

0 1 2 3 4 5 6 7 8 9

Linked List Implementation In C++ Using Friend Class

Linked List is one of the most common data structures available. In C++ we already have List in STL but in this program we will implement out own link list class using friend class.

#include <iostream>
using namespace std;

class Node
{
    friend class List;
    int val;
    Node *link; 
    public:
        Node() {
            val = 0;
            link = NULL;
        }
        Node(int v) {
            val = v;
            link = NULL;
        }
        Node(int v, Node *p) {
            val = v;
            link = p;
        }
};

class List
{
    int size;
    Node *head;
    public:
        List() {
            head = new Node();
            size = 0;
        }
        void append(int);
        void show() const;
        inline int len() {
            return size;
        }
};

void List::append(int item)
{
    Node *pivot = new Node(item);
    if (size == 0) {
        head->link = pivot;
    }
    else {
        Node *temp = head;
        while (temp->link != NULL) {
            temp = temp->link; 
        }
        temp->link = pivot;
    }
    size++;
}

void List::show() const
{
    Node *tmp = head->link;
    cout << "[";
    while (tmp != NULL) {
        cout << tmp->val << "," << ends;
        tmp = tmp->link;
    }
    cout << "\b\b]" << endl;
}

int main()
{
    List a;
    
    a.append(1);
    a.append(2);
    a.append(3);
    a.append(4);
    a.show();
    
    a.append(5);
    a.append(6);
    a.append(7);
    a.show();
    
    cout << "Length Of The List: "<< a.len() << endl;
    
    return 0;   
}

[1, 2, 3, 4]
[1, 2, 3, 4, 5, 6, 7]
Length Of The List: 7

--------------------------------
Process exited after 0.3124 seconds with return value 0
Press any key to continue . . .