# My Weblog

## Finding kth smallest element in Binary Tree

Today i was trying to hone my pointers skill since it was long time i used pointers. In the first year of my graduation when i was completely new to programming, my seniors told me that pointer is main concept in c. Since then i learned pointers and i did not use STL until started participating on Topcoder because everything was build in STL. During reading the Anderson tree on wiki , i thought to implement the kth smallest or largest element in binary tree. It was a good practice for pointers purpose. Now i am looking for some problem on which i can test this code.

```#include<cstdio>
#include<iostream>
#include<cstdlib>
using namespace std;

struct tree
{
int data,size;
struct tree *left,*right;
};
struct tree* insert(struct tree* t,int p)
{
if(t==NULL)
{
struct tree *tmp=(struct tree *)malloc(sizeof (struct tree));
tmp->data=p;
tmp->left=tmp->right=NULL;
tmp->size=1;
return tmp;
}
else if(p<=t->data)
{
t->size+=1;
t->left=insert(t->left,p);
}
else
{
t->size+=1;
t->right=insert(t->right,p);
}
return t;
}

struct tree* findkthsmallest(struct tree* t,int k)
{
int left_size=0;
if(t->left!=NULL) left_size=t->left->size;
if(left_size+1==k) return t;
else if(k<=left_size) return findkthsmallest(t->left,k);
else return findkthsmallest(t->right,k-left_size-1);//find k-left_size-1 smallest in right subtree.
}
struct tree* findkthlargest(struct tree* t,int k)
{

int right_size=0;
if(t->right!=NULL) right_size=t->right->size;
if(right_size+1==k) return t;
else if(k<=right_size) return findkthlargest(t->right,k);
else return findkthlargest(t->left,k-right_size-1);
}
int main()
{
struct tree *p,*q;
p=(struct tree*) malloc(sizeof (struct tree));
p=NULL;
int n;
while(scanf("%d",&n) && n!=-100) p=insert(p,n);
//print(p);
while(scanf("%d",&n)!=EOF){ if(n<=0 || n>p->size) continue; q=findkthlargest(p,n); printf("%d\n",q->data);}
}

```