Suppose we want to add the operation findKth to our repertoi

Suppose we want to add the operation findKth to our repertoire. The operation findKth(k) returns the kth smallest item in the tree. Assume all items are distinct. Explain how to modify the binary search tree to support this operation in O(logN) average time, without sacricing the time bounds of any other operation.(Java)

Solution

public class KthSmallest
{
public static void main(String[] args)
{
BST bst = new BST();//Create object
int[] arr =
{ 1,2,3,4,5,6,7,8,9 };
for (int num : arr)
bst.add(num);//add element to BST
int k=8;
System.out.println(\"Kth Smallest element is \"+bst.getOrdered(k));
  

}

private static class BST
{
Node root;//root node

public void add(int num) //Wrapper method for add
{
if (root == null)
{
root = new Node(num);
} else
add(root, num);
}

private void add(Node root, int num)//add node in BST
{
Node node = new Node(num);
if (node.value < root.value)
{
root.leftWeight++;
if (root.left == null)
root.left = node;
else
add(root.left, num);
} else
{
if (root.right == null)
root.right = node;
else
add(root.right, num);
}
}

public int getOrdered(int k)//Wrapper method to find kth smallest
{
return getOrdered(root, k);
}

private Integer getOrdered(Node root, int k)//Find smallest kth method
{
if (root == null)
return null;
if (root.leftWeight > k)
{
return getOrdered(root.left, k);
} else if (root.leftWeight < k)
{
return getOrdered(root.right, k - root.leftWeight);
} else
{
return root.value;
}
}
}

private static class Node
{
int value;
int leftWeight;
Node left;
Node right;

public Node(int value)
{
this.value = value;
this.leftWeight = 1;
}
}

}

=======================================================

output:

Kth Smallest element is 8

=======================================

Explanation:

We will augment the binary search tree by storing the weight of left subtree rooted at a node. So any node will keep an extra count which is equal to the number of nodes in its left subtree. This augmentation is called order statistics tree. With the help of this augmentation we can find the kth smallest element in O(log n) expected complexity for a balanced binary search tree. Suppose we try to find the 6th smallest element, we start at root. If root has leftWeight value 3, that means there are only 3 elements that are smaller than root. So 6th smallest element cannot be on the left side of root. So we try to find the element in right subtree. While going to right subtree we now try to find 6-4=2nd smallest element, because we already had 3 smaller element in root\'s left subtree and root itself is smaller than the right subtree. So we call the recursive function on root.right. If the value of k is less than the leftWeight then we just go to the left subtree with the value k.

==================================================

comment about work