[Leetcode] 230. Kth Smallest Element in a BST

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/?envType=study-plan-v2&envId=top-interview-150

initial

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        return find(root,k);
    }

    public int find(TreeNode node, int k){
        if(node==null) return;

        left = find(node.left,k)
        if(k==1) return node.val;
        k-=1;
        right = find(node.right,k)
        return 0;
    }
}

but even when i decrement k, it doesnt afffect the previous call stack's k value. It just affects k value in the curent call stack. So if we wanna mutate value k across all call stacks, we should use a class level variable.

sol

class Solution {
    int count = 0;
    int ans = Integer.MIN_VALUE;

    public int kthSmallest(TreeNode root, int k) {
        find(root,k);
        return ans;
    }

    public void find(TreeNode node, int k){
        if(node==null) return;

        find(node.left,k);
        count+=1;
        if(k==count){
            ans=node.val;
            return;
        } 
        find(node.right,k);
    }
}

complexity

n time worst case
1 space NO its recursion so depends on the call stack!!
log n if balanced, n if skewed.