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.

using namespace std;

struct tree 
		int data,size;
		struct tree *left,*right;
struct tree* insert(struct tree* t,int p)
			struct tree *tmp=(struct tree *)malloc(sizeof (struct tree));
			return tmp;
		else if(p<=t->data)
		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));
		int n;
		while(scanf("%d",&n) && n!=-100) p=insert(p,n);
		while(scanf("%d",&n)!=EOF){ if(n<=0 || n>p->size) continue; q=findkthlargest(p,n); printf("%d\n",q->data);}

April 7, 2010 - Posted by | Programming


  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: Logo

You are commenting using your 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: