Find Kth Smallest Value in BST -- K not changing

Question

I've mulled over this for so long it's frying my brain. It's possibly I don't fully understand recursion yet.

I don't understand why the value of k, after it equals reaches 0, does not go into the negatives. Instead it remains 0 until the helper function exists. I tried passing in an integer with an initial value of zero and adding until its value equaled k. However, this resulted in the same problem where once it equaled k, it remained that way.

Can someone please explain why the value stays the same?

class Solution {
        public int kthSmallest(TreeNode t, int k) {
          TreeNode tempNode = new TreeNode();
          int iter = 0;
          getKValue(t, k, tempNode); 
          return tempNode.val;
        }
        
        private static void getKValue(TreeNode t, int k, TreeNode temp) {
            if(t == null) {
                return;
            }
        
    
            getKValue(t.left, k, temp);
            
            
            k = k - 1;
            System.out.println(k);
            if(k == 0) {
                temp.val = t.val;
                return;
            }
            getKValue(t.right, k, temp);
        
        }
    }

For example, for the tree below the expected output is 1. But I get 3 and the console prints 0 twice.

Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1

Answer 1

I think the problem is because you are passing k across each recursive call. You shouldn't do that because that causes each recursive call to get their own copy of k. This means that when you modify k:

k = k - 1;

The other calls down the stack does not know about k changing. As far as the other calls are concerned, k is still 1, because they each have their own copy.

To fix this, you should have one shared k, that all the recursive calls can access:

    static int sharedK; // shared!
    public int kthSmallest(TreeNode t, int k) {
      TreeNode tempNode = new TreeNode();
      sharedK = k; // setting the sharedK
      getKValue(t, tempNode); 
      return tempNode.val;
    }
    
    private static void getKValue(TreeNode t, TreeNode temp) {
        if(t == null) {
            return;
        }

        getKValue(t.left, temp);
        
        sharedK--; // note the change here
        System.out.println(sharedK);
        if(sharedK == 0) {
            temp.val = t.val;
            return;
        }
        getKValue(t.right, temp);
    }

The same thing could be achieved if k were passed by reference, but unfortunately you can't pass by reference in Java.