static int count = 0;
public int KthSmallestElement(Node root, int k)
{
if(root == null)
return 0;
// Write your code here
KthSmallestElement(root.left,k);
count++;
if(count == k){
return root.data;
}
KthSmallestElement(root.right, k);
return -1;
}Hi Ayush
Please share your code using coding blocks ide so that i can help you more better by running your code. Also PLease share the question full statement along with constrains.
Given a BST and an integer K. Find the Kth Smallest element in the BST.
Example 1:
Input: 2 / \ 1 3 K = 2 Output: 2
Example 2:
Input: 2 / \ 1 3 K = 5 Output: -1
Your Task:
You don’t need to read input or print anything. Your task is to complete the function KthSmallestElement() which takes the root of the BST and integer K as inputs and return the Kth smallest element in the BST, if no such element exists return -1.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1<=Number of nodes<=100000
public int KthSmallestElement(Node root, int k)
{
if(root == null)
return 0;
// Write your code here
KthSmallestElement(root.left,k);
count++;
if(count == k){
return root.data;
}
KthSmallestElement(root.right, k);
return -1;
}
A simpler solution would be to do an inorder traversal and keep track of the element currently to be printed with a counter k. When we reach k, print the element. The runtime is O(n). Remember the function return type can not be void, it has to return its updated value of k after each recursive call. A better solution to this would be an augmented BST with a sorted position value at each node.
use this approach you will be able to solve it.
I just want to know where my approach is wrong
Your approach is taking O(h) auxillary space and we need to do this problem in O(1) . That is why you are not passing any test case.
And from next time Please share full code using coding blocks ide .com save your code there and then share the link so that i can easily run and debug your code.
@ayush_r18
I have ask you to share your full code so that i can run your code how can i run this function only can you please tell me??
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.