Kth Smallest Element in a BST

Java

public class Solution {
    /**
     * @param root: the given BST
     * @param k: the given k
     * @return: the kth smallest element in BST
     */
    
    public int quickSelectOnTree(TreeNode root, int k,HashMap<TreeNode, Integer> size) {
        if(root == null) {
            return -1;
        }
        int left = 0;
        if(root.left != null) {
            left = size.get(root.left);
        }
        if(left == k - 1) {
            return root.val;
        } 
        if(left >= k) {
            return quickSelectOnTree(root.left, k, size);
        } else {
            return quickSelectOnTree(root.right, k - 1 - left, size);
        }
    }
    
    
    public int getSize(TreeNode root, HashMap<TreeNode, Integer> size) {
        if(root == null) {
            return 0;
        }
        int sum = 1;
        sum += getSize(root.left, size);
        sum += getSize(root.right, size);
        size.put(root, sum);
        return sum;
    }
     
    public int kthSmallest(TreeNode root, int k) {
        // write your code here
        HashMap<TreeNode, Integer> size = new HashMap<>();
        getSize(root, size);
        
        return quickSelectOnTree(root, k, size);
    }
}