Returning Kth smallest element in a BST

0
votes

I wrote the following code snippet to return the Kth smallest element in a BST:

/**
 * 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) {
        if(root==NULL)
            return -2;
        cout<<"Root value "<<root->val<<" and k value "<<k<<"\n";

        kthSmallest(root->left, k-1);
        if((k)==0)
            return root->val;
        kthSmallest(root->right, k-1);
    }
};

I basically just do an inorder traversal of the tree and decrement the value of k during each recursive call. So, in this way, when the value of k equals 0, I have found the node and just return it.

Following is the output of my debugging statements:

Root value 1 and k value 3
Root value 2 and k value 2
Root value 4 and k value 1
Root value 8 and k value 0
Root value 9 and k value 0
Root value 5 and k value 1
Root value 10 and k value 0
Root value 11 and k value 0
Root value 3 and k value 2
Root value 6 and k value 1
Root value 12 and k value 0
Root value 7 and k value 1

I am unable to understand why the program keeps on executing even after k has become 0. What have I missed? I appreciate your help.

Edit: I don't think the question description is required, but if needed, it can be found here: LeetCode: Find Kth smallest element in a BST. Also, please note that I cannot edit the function prototype. Also, the question says that the k would be a valid number between 1 and BST's total number of elements.

2
c++
What are you doing with the value that the recursive calls to kthSmallest returns? - Some programmer dude
If the value of k used during that recursive call was not 0, then I just ignore it. - user8177388
Then why bother returning anything to begin with, if you just ignore it? - Some programmer dude
As for your problem, you return from the recursive calls when k == 0, but in the calling function k != 0. Please learn how to use a debugger to step through your code line by line, stepping into the recursive calls. That should make it much clearer what happens. - Some programmer dude
Could you kindly elaborate? I am returning a value because my overall function should return the Kth smallest element. Ideally, I wish the value is returned only when k==0. - user8177388

2 Answers

0
votes

Variables are not shared between (recursive or not) calls. Each call will have k being a normal local variable whose value is promptly forgotten once the function returns.

If you have k == 1 and then do kthSmallest(root->left, k-1) it's only in the recursive call that k == 0. In the callee the value of k is still 1.

This algorithm will never work as coded, because you rely on arguments and local variables being shared.

You also don't propagate the K:th smallest value from the bottom of the call tree. You just throw it away, and in the end (the very first call to kthSmallest) don't return anything which leads to undefined behavior.

0
votes

You code would not work as is, as in the previous comment. You could do something along the lines of:

int kthSmallest(TreeNode* root, int k) {
    int i = 0;
    return kthSmallest(root, &i, k);
}

int kthSmallest(TreeNode* root, int *i, int k) {
    if(root == nullptr)
        return INT32_MAX;

    int left = kthSmallest(root->left, i, k);

    if (left != INT32_MAX)
        return left;

    if (++*i == k)
        return root->val;

    kthSmallest(root->right, i, k);
}