Easiest solution using heap


#1

void preorder(TreeNode* A,int B,priority_queue& q)
{
if(A==NULL)
return;
q.push(A->val);
if(q.size()>B)
q.pop();
preorder(A->left,B,q);
preorder(A->right,B,q);
}
int Solution::kthsmallest(TreeNode* A, int B) {
priority_queue q;
preorder(A,B,q);
return q.top();
}


#2

Please tell what is the time complexity of this code.


#3

Each push or pop operation in a priority_queue is O(logK) and there are N nodes, so O(NlogK).


#4

Inorder traversal prints the elements in sorted order for BST
return inOrderTraversal[k] -> O(N)