Binary Search Tree之所以被大家喜愛(ài)，就是因?yàn)樗慕Y(jié)構(gòu)很方便大家查找某一個(gè)元素
大家都知道， BST的結(jié)構(gòu)是 Root的左半邊所有節(jié)點(diǎn)都比Root小， Root的右半邊所有節(jié)點(diǎn)都比Root的大。并且，所有子tree 都包含了這個(gè)特點(diǎn)。 比如上圖，Root 為50，root左半部分所有的節(jié)點(diǎn)都比50小，右邊所有節(jié)點(diǎn)都比50大。 再看看子tree。 17位left subtree的root。12比17小吧， 23比17大吧。?
在這個(gè)結(jié)構(gòu)下，最小的元素一定是在最左下角。 上圖中就是9. 第二小的元素是9的爸爸，12， 第三小的是subroot的右邊，14. 而12,9,14 這幾個(gè)東西如果看成一整個(gè)節(jié)點(diǎn)的話，這個(gè)節(jié)點(diǎn)的爸爸17就是下一個(gè)最小的元素，然后再往右走，19，23.
這種走法就是典型的in-order traversal. 那么找kth-element其實(shí)也就是判斷一下我們in-order了有沒(méi)有K次。
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
