My Weblog

Blog about programming and math

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);}
	}
		
Advertisements

April 7, 2010 - Posted by | Programming

2 Comments »

  1. Are you building Binary Tree or Binary Search Tree. I hope you are trying to search Kth Largest or Kth Smallest node in BST.

    Comment by Anonymous | May 5, 2010 | Reply

    • I think it should be valid for both as long as i know at any node i how many children in left subtree and right subtree. I created a binary search tree in code for testing purpose.

      Comment by tiwari_mukesh | May 5, 2010 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: