PU Kth Smallest Element in a BST

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?

C Solution:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void inorder(struct TreeNode *root, int *ind, int k, int *res) {
    if (*ind == k) return;
    if (root->left) inorder(root->left, ind, k, res);
    ++*ind;
    if (*ind == k) *res = root->val;
    if (root->right) inorder(root->right, ind, k, res);
}
int kthSmallest(struct TreeNode* root, int k) {
    int ind = 0, res;
    inorder(root, &ind, k, &res);
    return res;
}

Summary:

• Worst time complexity: O(n + k), space complexity: O(n)
• Best time complexity: O(k), space complexiyt: O(k)
• For followup: add a count field in TreeNode structure.

LeetCode: 230. Kth Smallest Element in a BST