Home > Algorithms > kth smallest element without using any static/global variable in Binary Search Tree

kth smallest element without using any static/global variable in Binary Search Tree

July 7, 2012

public BSTNodeSize findKth (int k, BSTNodeSize t) {
if (t == null)
throw new IllegalArgumentException();
int lsize= 0; // size of left subtree
if (t.left != null)
lsize= ((BSTNodeSize)(t.left)).size;
if (k = lsize + 1)
return t;
if (k < = lsize)
return findKth(k, (BSTNodeSize)t.left);
return findKth(k – lsize – 1, (BSTNodeSize)t.right);
}
Advertisements
Categories: Algorithms
%d bloggers like this: