Show how to augment the ordinary Binary Search Tree (BST) datastructure so that it supports an efficient procedure which, oninput (x, k) where x is the root of a BST and k an integer, outputthe k-th smallest number store in the BST. Let n denote the totalnumber of elements stored in the BST, what is the running time ofyour efficient procedure? How does your modification of the BSTdata structure affect the performance of other BST operations wediscussed in class?
