laxman601
BAN USERclass KthLargestBST{
protected static int findKthLargest(BSTNode root,int k){
int [] result=findKthLargest(root,k,0);
return result[1];//the element we are looking for.
}
private static int[] findKthLargest(BSTNode root,int k,int count){//returns an array containing 2 ints..one for counts and the other for result.
if(root==null){
int[] i=new int[2];
i[0]=-1;
i[1]=-1;
return i;
}else{
int rval[]=new int[2];
int temp[]=new int[2];
rval=findKthLargest(root.rightChild,k,count);
if(rval[0]!=-1){
count=rval[0];
}
count++;
if(count==k){
rval[1]=root.data;
}
temp=findKthLargest(root.leftChild,k,(count));
if(temp[0]!=-1){
count=temp[0];
}
if(temp[1]!=-1){
rval[1]=temp[1];
}
rval[0]=count;
return rval;
}
}
public static void main(String args[]){
BinarySearchTree bst=new BinarySearchTree();
bst.insert(6);
bst.insert(8);
bst.insert(7);
bst.insert(4);
bst.insert(3);
bst.insert(4);
bst.insert(1);
bst.insert(12);
bst.insert(18);
bst.insert(15);
bst.insert(16);
bst.inOrderTraversal();
System.out.println();
System.out.println(findKthLargest(bst.root,7));
}
}
- laxman601 March 14, 2013
I think the above code will not work for all cases. for example, consider what happens when the input is "EABCD" with the preference array now changed to {4,1,2,3,4} The answer should be 1.Since in one pass it rotates to "ABCDE" where 4 are happy.
Also, bestPassesNum should point to the index to yield correct answer. Its pointing to the maximum number.
I've made some modifications.please let me know if its wrong.
- laxman601 March 19, 2013