K’th Smallest Element in 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?

Solution: Divide and Conqur

    int kthSmallest(TreeNode* root, int k) {
        int cnt = count(root->left);
        if (k <= cnt) {
            return kthSmallest(root->left, k);
        } else if (k > cnt + 1) {
            return kthSmallest(root->right, k - cnt - 1);
        }
        return root->val;
    }
    int count(TreeNode* node) {
        if (!node) return 0;
        return 1 + count(node->left) + count(node->right);
    }

Solution: Inorder Traversal Iterative

    int kthSmallest(TreeNode * root, int k) {
        // write your code here
        if (!root) return 0;

        int count = 0;
        stack<TreeNode*> s;
        TreeNode *cur = root;        
        while (!s.empty() || cur) {
            if (cur) {
                s.push(cur);
                cur = cur->left;
            } else {
                TreeNode *node = s.top();
                cur = node->right;

                count += 1;
                if (count == k) return node->val;

                s.pop();
            }
        }

        return 0;
    }

Solution: Maintain the rank of each node

int kthSmallestUtil(TreeNode *root, int k, int &c) {
    if (!root || c > k) return INT_MIN;

    int result = kthSmallestUtil(root->left, k, c);
    if (c == k) return result;

    c += 1;
    if (c == k) return root->val;

    result = kthSmallestUtil(root->right, k, c);
    if (c == k) return result;

    return INT_MIN;
}

int kthSmallest(TreeNode * root, int k) {
    // write your code here
    int index = 0;
    return kthSmallestUtil(root, k, index);
}

Solution: Inorder Traversal

Time complexity: O(n) where n is total nodes in tree..

void inorder(TreeNode *root, vector<int> &arr) {
    if (!root) return;
    inorder(root->left, arr);
    arr.push_back(root->val);
    inorder(root->right, arr);
}

int kthSmallest(TreeNode * root, int k) {
    // write your code here
    vector<int> arr;
    inorder(root, arr);
    return arr[k-1];
}