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?

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void helper(TreeNode *root, int k, int& counter, int& ans) {
        if (root == NULL) {
            return;
        }
        helper(root -> left, k, counter, ans);
        counter++;
        if (counter == k) {
            ans = root -> val;
            return;
        }
        helper(root -> right, k, counter, ans);
        return;
    }
    int kthSmallest(TreeNode* root, int k) {
        int counter = 0, ans;
        helper(root, k, counter, ans);
        return ans;
    }
};

========= Follow up Leetcode ======

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?

Insert and delete in a BST were discussed last week, the time complexity of these operations is $\mathcal{O}(H)$, where $H$ is a height of binary tree, and $H = \log N$ for the balanced tree.

Hence without any optimisation insert/delete + search of kth element has $\mathcal{O}(2H + k)$ complexity. How to optimise that?

That's a design question, basically we're asked to implement a structure which contains a BST inside and optimises the following operations :

• Insert
• Delete
• Find kth smallest

Seems like a database description, isn't it? Let's use here the same logic as for LRU cache design, and combine an indexing structure (we could keep BST here) with a double linked list.

Such a structure would provide:

• $\mathcal{O}(H)$ time for the insert and delete.
• $\mathcal{O}(k)$ for the search of kth smallest.

The overall time complexity for insert/delete + search of kth smallest is $\mathcal{O}(H + k)$ instead of $\mathcal{O}(2H + k)$.

Complexity Analysis

• Time complexity for insert/delete + search of kth smallest: $\mathcal{O}(H + k)$, where $H$ is a tree height. $\mathcal{O}(\log N + k)$ in the average case, $\mathcal{O}(N + k)$ in the worst case.
• Space complexity : $\mathcal{O}(N)$ to keep the linked list.

============== another approach ========

class Solution { public: int kthSmallest(TreeNode* root, int k) { int cnt = countNodes(root->left); if (cnt == k - 1) return root->val; else if (cnt > k - 1) return kthSmallest(root->left, k); else return kthSmallest(root->right, k - cnt - 1); } int countNodes(TreeNode *root) { if (root == nullptr) return 0; return 1 + countNodes(root->left) + countNodes(root->right); } };

======== Another attempt ====

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int kthSmallest(TreeNode* root, int k) { int counter = 0; int ans; bool ansFound = false; helper(root, counter, ans, k, ansFound); return ans; } void helper(TreeNode *root, int& counter, int& ans, int k, bool& found) { if (root == NULL || found) { return; } helper(root -> left, counter, ans, k, found); counter++; if (counter == k) { ans = root -> val; found = true; return; } helper(root -> right, counter, ans, k, found); } };

=========== O(log n + k) is the answer =====

Approach 1: Recursion

It's a very straightforward approach with $\mathcal{O}(N)$ time complexity. The idea is to build an inorder traversal of BST which is an array sorted in the ascending order. Now the answer is the k - 1th element of this array.

Complexity Analysis

• Time complexity : $\mathcal{O}(N)$ to build a traversal.
• Space complexity : $\mathcal{O}(N)$ to keep an inorder traversal. 
  

---

Approach 2: Iteration

The above recursion could be converted into iteration, with the help of stack. This way one could speed up the solution because there is no need to build the entire inorder traversal, and one could stop after the kth element.

Complexity Analysis

• Time complexity : $\mathcal{O}(H + k)$, where $H$ is a tree height. This complexity is defined by the stack, which contains at least $H + k$ elements, since before starting to pop out one has to go down to a leaf. This results in $\mathcal{O}(\log N + k)$ for the balanced tree and $\mathcal{O}(N + k)$ for completely unbalanced tree with all the nodes in the left subtree.
• Space complexity : $\mathcal{O}(H + k)$, the same as for time complexity, $\mathcal{O}(N + k)$ in the worst case, and $\mathcal{O}(\log N + k)$ in the average case.