// slip1Q.1)Implement a Binary search tree (BST) library (btree.

h) with operations –
create, insert, inorder.
#include <stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;

};
typedef struct node node;
node *create(int data)
{
node *newnode=(node *)malloc(sizeof(node));
newnode->data=data;
newnode->left=NULL;
newnode->right=NULL;
return newnode;
}
node *insert(node *root,int data)
{
if(root==NULL)
{
return create(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(node *root)
{

/*this line is important because it is a base condition*/

if(root!=NULL)
{
inorder(root->left);
printf(" %d\n",root->data);
inorder(root->right);
}
}
void preorder(node *root)
{
 /*this line is important because it is a base condition*/
if(root!=NULL)
{
printf(" %d\n",root->data);
preorder(root->left);

preorder(root->right);
}
}
void postorder(node *root)
{

/*this line is important because it is a base condition*/

if(root!=NULL)
{
postorder(root->left);
postorder(root->right);
printf(" %d\n",root->data);
}
}
int main() {
node *root=NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);
printf("the data of tree are by inorder traversal is\n");
inorder(root);
//yaha pe agar hme pucha ki preorder do to sirf inorder ko preorder me chnage kar
dena hai aur upar wale me sirf preorder function ko rakhna hai baki inorder aur
postorder ko delete
return 0;
}
____________________________________________________________________________________
______________________
adjacency matix create karne ka way
________________________________________
#include<stdio.h>
#include<stdlib.h>
#define max 10
void input(int adjmat[][max],int tnode)
{
for(int i=0;i<tnode;i++)
{
for(int j=0;j<tnode;j++)
{
printf("enter edge from source to dest (1 if edge is present otherwise
0)");
scanf("%d",&adjmat[i][j]);
}
}
}
void display(int adjmat[][max],int tnode)
{
for(int i=0;i<tnode;i++)
{
for(int j=0;j<tnode;j++)
{
printf("%d",adjmat[i][j]);
}
printf("\n");
}
}
int main()
{
int adjmat[max][max]={0};
int src,dest;
int tnode;
printf("enter total number of nodes\n");
scanf("%d",&tnode);
input(adjmat,tnode);
printf("total nodes are\n");
display(adjmat,tnode);

}
___________________________________________________________
now jab jab hme indegree puchega hme hamesa phle adjacency matrix create karna hai
aur agar adjacency list pucha tab bhi adjacency matrix create karna hai
___________________________________________________
indegree kaise nikale uska function with adjacency matrix

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

#define MAX 10

void input(int adjmat[][MAX], int tnode) {

for (int i = 0; i < tnode; i++) {
for (int j = 0; j < tnode; j++) {
printf("Enter edge from node %d to node %d (1 if edge exists, otherwise
0): ", i, j);
scanf("%d", &adjmat[i][j]);
 }
}
}

void display(int adjmat[][MAX], int tnode) {

printf("\nAdjacency Matrix:\n");
for (int i = 0; i < tnode; i++) {
for (int j = 0; j < tnode; j++) {
printf("%d ", adjmat[i][j]); // Added space for better readability
}
printf("\n");
}
}

void indegree(int adjmat[][MAX], int tnode) {

int indegree[MAX] = {0}; // Initialize all indegrees to 0

// Compute indegree by counting incoming edges

for (int j = 0; j < tnode; j++) {//alway ispe dyan dena hai jab indegree puche
to j upar aur jab outdgree puche to i phle
for (int i = 0; i < tnode; i++) {
if (adjmat[i][j] == 1) {
indegree[j]++;
}
}
}

// Print the indegrees

printf("\nIndegree of each node:\n");
for (int i = 0; i < tnode; i++) {
printf("Node %d: Indegree = %d\n", i, indegree[i]);
}
}

int main() {
int adjmat[MAX][MAX] = {0};
int tnode;

printf("Enter total number of nodes: ");

scanf("%d", &tnode);

input(adjmat, tnode);
display(adjmat, tnode);

printf("\nIndegree elements:\n");
indegree(adjmat, tnode);

return 0;
}
**************************************
adjacency list
*****
iske liye bhi hm adjacency matrix use karenge
*********************
#include <stdio.h>
#include <stdlib.h>

#define MAX 10

// Structure for adjacency list node

struct node {
int vertice;
struct node *next;
};

typedef struct node Node;

// Function to add an edge to the adjacency list

void addEdge(Node *adjList[], int src, int dest) {
// Create a new node for destination
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->vertice = dest;
newNode->next = adjList[src]; // Point to existing list**imp
adjList[src] = newNode;
}

// Function to convert adjacency matrix to adjacency list

void adjacencyList(int adjmat[][MAX], Node *adjList[], int tnode) {
for (int i = 0; i < tnode; i++) {
adjList[i] = NULL; // Initialize adjacency list**imp
for (int j = 0; j < tnode; j++) {
if (adjmat[i][j] == 1) {
addEdge(adjList, i, j);
}
}
}
}

// Function to print adjacency list

void displayAdjList(Node *adjList[], int tnode) {
printf("\nAdjacency List Representation:\n");
for (int i = 0; i < tnode; i++) {
printf("Node %d:", i);
Node *temp = adjList[i];
while (temp!=NULL) {
printf(" -> %d", temp->vertice);
temp = temp->next;
}
printf("\n");
 }
}

// Function to input adjacency matrix

void input(int adjmat[][MAX], int tnode) {
for (int i = 0; i < tnode; i++) {
for (int j = 0; j < tnode; j++) {
printf("Enter edge from node %d to node %d (1 if edge exists, otherwise
0): ", i, j);
scanf("%d", &adjmat[i][j]);
}
}
}

void displayMatrix(int adjmat[][MAX], int tnode) {

printf("\nAdjacency Matrix:\n");
for (int i = 0; i < tnode; i++) {
for (int j = 0; j < tnode; j++) {
printf("%d ", adjmat[i][j]);
}
printf("\n");
}
}

int main() {
int adjmat[MAX][MAX] = {0};
Node *adjList[MAX]; // array of linked list
int tnode;

printf("Enter total number of nodes: ");

scanf("%d", &tnode);

input(adjmat, tnode);
displayMatrix(adjmat, tnode);

// Convert adjacency matrix to adjacency list

adjacencyList(adjmat, adjList, tnode);

// Display adjacency list

displayAdjList(adjList, tnode);

return 0;
}

****************************
dfs using stack
****************************
#include <stdio.h>
#include <stdlib.h>
#define MAX 10

int stack[MAX];
int visit[MAX];
int top = -1;

void push(int value) {

if (top == MAX - 1) {
printf("Stack Overflow\n");
return;
}
stack[++top] = value;
}

int pop() {
if (top == -1) {
printf("Stack Underflow\n");
return -1;
}
return stack[top--];
}

int isempty() {
return top == -1;
}

void dfsiterative(int adjmat[][MAX], int start, int tnode) {

for (int i = 0; i < tnode; i++) {
visit[i] = 0;
}

push(start);

while (!isempty()) {
int node = pop();

if (!visit[node]) {
printf("%d ", node);
visit[node] = 1;
}

for (int i = tnode - 1; i >= 0; i--) {

if (adjmat[node][i] == 1 && !visit[i]) {
push(i);
}
}
}
}
void input(int adjmat[][MAX], int tnode) {
int edges, src, dest;
printf("Enter the number of edges: ");
scanf("%d", &edges);

for (int i = 0; i < edges; i++) {

printf("Enter edge (source destination): ");
scanf("%d %d", &src, &dest);
adjmat[src][dest] = 1;
adjmat[dest][src] = 1;
}
}
void display(int adjmat[][MAX], int tnode) {
printf("Adjacency Matrix:\n");
for (int i = 0; i < tnode; i++) {
for (int j = 0; j < tnode; j++) {
printf("%d ", adjmat[i][j]);
}
printf("\n");
}
}

int main() {
int adjmat[MAX][MAX] = {0};
int tnode, start;

printf("Enter total number of nodes: ");

scanf("%d", &tnode);

printf("Enter the node from where you want to start DFS: ");
scanf("%d", &start);

input(adjmat, tnode);
display(adjmat, tnode);

printf("DFS Traversal:\n");
dfsiterative(adjmat, start, tnode);

return 0;
}
____________________________________________________
comparision binary search tree:

***************************
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
 struct node *left;
struct node *right;
}node;
node *create(int data)
{
node *newnode=(node *)malloc(sizeof(node));
newnode->data=data;
newnode->left=NULL;
newnode->right=NULL;
return newnode;
}
node *insert(node *root,int data)
{
if(root==NULL)
{
return create(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(node *root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%d\n",root->data);
inorder(root->right);
}
}
int compare(node *root1,node *root2)
{
if(root1==NULL && root2==NULL)
{
return 1;
}
if(root1==NULL || root2==NULL)
{
return 0;
}
return root1->data==root2->data && compare(root1->left,root2->left)&&
compare(root1->right,root2->right);
}
int main()
{
node *root1=NULL,*root2=NULL;
root1=insert(root1,5);
insert(root1,7);
insert(root1,6);
inorder(root1);

printf("\n");
root2=insert(root2,5);
insert(root2,7);
insert(root2,6);
inorder(root2);
int flag= compare(root1,root2);
if(flag)
{
printf("they both are identical to each other\n");
}
else
{
printf("they are not same");
}

}
***************************************
count leafnode && totalnode && non leafnode(sayad yah niiaaya hai ek bar dekh lena)
***********************************
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *left;
struct node *right;
}node;
node *create(int data)
{
node *newnode=(node *)malloc(sizeof(node));
newnode->data=data;
newnode->left=NULL;
newnode->right=NULL;
return newnode;
}
node *insert(node *root,int data)
{
if(root==NULL)
{
return create(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(node *root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%d\n",root->data);
inorder(root->right);
}
}
int counttotnode(node *root)
{
if(root==NULL)
{
return 0;
}
return 1+counttotnode(root->left)+counttotnode(root->right);
}
int countleafnode(node *root)
{
if(root==NULL)
{
return 0;
}
if(root->left==NULL && root->right==NULL)
{
return 1;
}
return countleafnode(root->left)+countleafnode(root->right);
}
int countnonleafnode(node *root)
{
if(root==NULL||(root->left==NULL && root->right==NULL))
{
return 0;
}
return 1+countnonleafnode(root->left)+countnonleafnode(root->right);
}
int main()
{
node *root1=NULL,*root2=NULL;
 root1=insert(root1,5);
insert(root1,2);
insert(root1,6);
inorder(root1);
int totalnode=counttotnode(root1);
printf("the total node is %d\n",totalnode);
int countleaf=countleafnode(root1);
printf("the countleaf are=%d\n",countleaf);
int nonleaf=countnonleafnode(root1);
printf("the total number of nonleaf node=%d\n",nonleaf);
}

-------------------------------------------*************
adjacency matrix and indegree
******************************************************
#include<stdio.h>
#include<stdlib.h>
#define max 10
void input(int adjmat[][max],int tnode)
{
for(int i=0;i<tnode;i++)
{
for(int j=0;j<tnode;j++)
{
printf("enter element from source(%d) to dest(%d)\n",i,j);
scanf("%d",&adjmat[i][j]);
}
}
}
void display(int adjmat[][max],int tnode)
{
for(int i=0;i<tnode;i++)
{
for(int j=0;j<tnode;j++)
{
printf("%d ",adjmat[i][j]);
}
printf("\n");
}
}
void indegree(int adjmat[][max],int tnode)
{
int indegree[max]={0};
for(int j=0;j<tnode;j++)
{
for(int i=0;i<tnode;i++)
{
if(adjmat[i][j]==1)
{
indegree[j]++;
 }
}
}
for(int i=0;i<tnode;i++)
{
printf("%d is node with indegree %d\n",i,indegree[i]);
}
}
int main()
{
int adjmat[max][max];
int tnode,src,dest;
printf("enter totalnumber of edges:\n");
scanf("%d",&tnode);
input(adjmat,tnode);
display(adjmat,tnode);
indegree(adjmat,tnode);
}
*************************************************
adjacency matrix and adjacency list
************************************************
#include<stdio.h>
#include<stdlib.h>
#define max 10
typedef struct node
{
int vertice;
struct node *next;
}node;

void input(int adjmat[][max],int tnode)

{
for(int i=0;i<tnode;i++)
{
for(int j=0;j<tnode;j++)
{
printf("enter element from source(%d) to dest(%d)\n",i,j);
scanf("%d",&adjmat[i][j]);
}
}
}
void display(int adjmat[][max],int tnode)
{
for(int i=0;i<tnode;i++)
{
for(int j=0;j<tnode;j++)
{
printf("%d ",adjmat[i][j]);
}
printf("\n");
 }
}
void addedge(node *adjlist[],int src,int dest)
{
node *newnode=(node *)malloc(sizeof(node));
newnode->vertice=dest;
newnode->next=adjlist[src];
adjlist[src]=newnode;
}
void adjacencylist(int adjmat[][max],node *adjlist[],int tnode)
{
for(int i=0;i<tnode;i++)
{
adjlist[i]=NULL;
for(int j=0;j<tnode;j++)
{
if(adjmat[i][j]==1)
{ //i is source and j is dest
addedge(adjlist,i,j);
}
}
}
}
void displayadjlist(node *adjlist[],int tnode)
{
for(int i=0;i<tnode;i++)
{
printf("Node %d:",i);
node *temp=adjlist[i];
while(temp!=NULL)
{
printf("--> %d",temp->vertice);
temp=temp->next;
}
printf("\n");
}
}
int main()
{
int adjmat[max][max]={0};
int tnode;
tnode,src,dest;
node *adjlist[max];
printf("enter totalnumber of nodes:\n");
scanf("%d",&tnode);
input(adjmat,tnode);
display(adjmat,tnode);
printf("below are for the adjacnecy list\n");
adjacencylist(adjmat,adjlist,tnode);
displayadjlist(adjlist,tnode);
}