Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 

You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

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?

 

Analyse:

Trial 1: We can first sort the sequence by inorder traversal and find the k-th element.

　　　　Runtime: 24ms

1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     int kthSmallest(TreeNode* root, int k) {13         if(!root) return 0;14         vector
     
       result;15         inorder(root, result);16         return result[k - 1];17     }18     void inorder(TreeNode* root, vector
      
       & result){19         if(!root) return;20         inorder(root->left, result);21         result.push_back(root->val);22         inorder(root->right, result);23     }24 };
      
     

 

Trial 2: Do the inorder process iterately, set a count number, when it equals to k, return corresponding value.

        　Runtime: 24ms.

1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     int kthSmallest(TreeNode* root, int k) {13         if(!root) return 0;14         stack
     
       stk;15         int order = 0;16         while(!stk.empty() || root){17             if(root){18                 stk.push(root);19                 root = root->left;20             }21             else{22                 root = stk.top();23                 stk.pop();24                 order++;25                 if(order == k) return root->val;26                 root = root->right;27             }28         }29     }30 };