Kth Smallest Element in BST

Solution 1 : In-Order + global counter.

Solution 2 : Augment BST.

Solution 3 : Binary Search :) Interesting (actually Augment BST)

    // Time : (log n * n)
    // Time : O(log n) + O(n) ? 
    public int kthSmallest (TreeNode root) {
         //count # in left subtree.
         int count = 0;
         //change here
         if (map.contains(root.left)) {
             count = map.get(root.left);
         } else {
             count = countNodes(root.left);
         }
         if (k == count + 1) {
             return root.val;
         }
         //in left 
         if (k <= count) {
             return kthSmallest(root.left,k);
         } else {
             return kthSmallest(root.right,k);
         }   
     }
     //redundant calculation, actually we could use map to store all numbers smaller than itself.
     public int countNodes(TreeNode root) {
           if (root == null) {
               return 0;
           }
           return 1 + countNodes(root.left) + countNodes(root.right);
     }

Solution 4 : Optimized Solution 3. (Augment BST).

      public int countNodes(TreeNode root) {
           if (root == null) {
               return 0;
           }
           int left = countNodes(root.left);
           map.put(root,left); 
           return 1 + left + countNodes(root.right);
     }