 # Need solution complexity calculation

Can anybody tell me what is the space and time complexity of this solution
It is finding the kth smallest element in BST

void kthSmallestUtil(Node* root, int k,int &count, int &ans)
{

``````if(root == NULL || count  >= k){
return;
}

kthSmallestUtil(root->left, k, count,  ans);

count++;
if(count == k){
ans = root->data;
return;
}

kthSmallestUtil(root->right, k, count,  ans);
``````

}

int KthSmallestElement(Node* root, int k){

``````int count = 0;
int ans = -1;
kthSmallestUtil(root, k, count, ans);
return ans;
``````

}

time compexity is logn because for travelling upto least it takes logn and plus k paths
total log(n) +k==log(n);

space complexity is constant o(1) because we are not using any extra space for traversals;

I would disagree with @harshakunchala.

Space complexity would be O(N) where N is the number of nodes in the BST. This is because for each node in the BST, you will store some constant number of items. In case of finding Kth smallest you only need value at current node, and size of subtree rooted at current node.

Time complexity is also O(N). This is because, O() notation denotes the upper bound on number of operations. And, in the worst-case scenario, which here is that the BST is just a straight path, you will have time complexity O(N).