binary search tree ( insert, kth smallest, inorder, delete by key)

#include <stdio.h>

#include <stdlib.h>

struct node

{

int key;

int k;

struct node* left;

struct node* right;

};

typedef struct node* TREE;

TREE makenode(int key);

TREE insert(TREE root, int key);

void insert2(TREE root, int key);

TREE deletenode(TREE root);

TREE deletekey(TREE root, int key);

TREE insertrightmost(TREE a, TREE b);

void inorder(TREE root);

void printk(TREE root,int k);//kth smallest

int main(void)

{

TREE root=NULL;

int i;

root = insert(root, 4);

root = insert(root, 2);

root = insert(root, 1);

root = insert(root, 3);

insert2(root,6);

insert2(root,5);

insert2(root,7);

inorder(root);

printf("\n");

//printk(root,1);

//printk(root,2);

for (i=0;i<7;i++)

printk(root,i+1);

//root = deletekey(root,4);

root = deletekey(root,7);

inorder(root);

}

TREE makenode(int key)

{

TREE temp = (TREE)malloc(sizeof(struct node));

temp->key=key;

temp->left=NULL;

temp->right=NULL;

temp->k= 1;

return temp;

}

TREE insert(TREE root, int key)

{

if (root == NULL){

return makenode(key);

}

if (root->key > key)

{

root->k++;

root -> left = insert(root->left,key);

}

else if (root->key < key)

{

root->right = insert(root->right,key);

}

return root;

}

void insert2(TREE root, int key)

{

if (root == NULL){

root = makenode(key);

return;

}

if (root->key > key){

if (root->left == NULL){

root->k++;

root->left = makenode(key);

return;

}

root->k++;

insert(root->left,key);

}

else if (root->key < key){

if (root->right == NULL){

root->right= makenode(key);

return;

}

insert(root->right,key);

}

}

TREE insertrightmost(TREE a, TREE b)

{

if (a == NULL)

return b;

a->right = insertrightmost(a->right,b);

return a;

}

TREE deletenode(TREE root)

{

TREE temp, lefttemp;

temp=root->right;

//temp->left = root->left;

if (root->right && root->right->left)

{

root->left = insertrightmost(root->left,root->right->left);

}

if (root->left)

temp->left = root->left;

if (temp && temp->right)

temp->right->left=NULL;

root = temp;

return root;

}

TREE deletekey(TREE root, int key)

{

if (root==NULL)

return NULL;

if (root->key == key)

{

root= deletenode(root);

}

else if (root->key > key)

{

root ->left = deletekey(root->left,key);

}

else //if (root -> key < key)

{

root ->right = deletekey(root->right,key);

}

return root;

}

void printk(TREE root,int k)

{

if (root->k == k)

{

printf ("%d\n",root->key);

}

else if (k > root->k)

{

printk(root->right, k - (root->k));

}

else

{

printk(root->left,k);

}

}

void inorder(TREE root)

{

if (root == NULL)

return;

inorder(root->left);

printf ("%d ",root->key);

inorder(root->right);

}