Why does my program to return the kth smallest element in a BST not work?

71 views Asked by At

so I'm supposed to write a program to print the kth smallest element in a binary search tree. This is the code I have. Sad as this is, I've been staring at my code for 45 minutes and I just can't seem to find my mistake. Could someone help me out?

let res;

function kthLargestInBST(t, k) {   
    helper(t, k, 1);
    return res;
}

function helper(t, k, curr) {
    if (t === null) return;

    helper(t.left, k, curr);
    if (curr === k) {
        res = t.value;
    }
    curr++;
    helper(t.right, k, curr);
}
1

There are 1 answers

0
Alexander Pavlov On

curr variable is local function parameter, when you modify it then its new value is NOT available at upper level. In other words, when you go one level up then its values is reset to 1.

must be something like that

function kthLargestInBST(t, k) {   
    var q = {curr:1, res:null} 
    helper(t, k, q);
    return q.res;
}
// returns true if found the result 
function helper(t, k, q) {
    if (t === null) return false;

    if (helper(t.left, k, q)) return true;
    if (q.curr === k) {
        q.res = t.value;
        return true;  
    }
    q.curr++;
    return helper(t.right, k, q);
}