Naive solution
A naive approach would be to perform an inorder traversal of the BST, store the result in an array and return the kth element of that array. Time complexity: O(n) where n is the total number of nodes Space complexity: O(n)
Controlled inorder traversal
A controlled inorder traversal can be done using the iterative form of inorder traversal. Please see the solution of LC 94 for a clear understanding of the iterative traversal.
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode*> s;
while (!s.empty() || root) {
while (root) {
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
if (--k == 0) return root->val;
root = root->right;
}
return -1; // we will not reach this statement as k is always <= number of nodes
}
Time complexity: O(H+k), where H 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 O (logN + k) for the balanced tree and O(N+k) for completely unbalanced tree with all the nodes in the left subtree. Space complexity: O(H+k), the same as for time complexity.