230. Kth Smallest Element in a BST

Question

in c++ we can change the value of variable though pointers and references in another function but we cannot do it in java . Let me come back to the query

This is the problem description, Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Integer cnt = 1, ans = 0;
        traverse(root, k , cnt, ans);
        return ans;
        
    }
    
    void traverse(TreeNode root, int k, Integer cnt, Integer ans){
        if(root == null) return;
        
        traverse(root.left, k, cnt, ans);
        if(cnt++ == k){
            ans = new Integer(root.val);
            return;
        }
        traverse(root.right, k, cnt, ans);

    }
}

Suppose I want to change the value of ans through traverse function which is void and does not return anything but wants to change the value of ans how can I do that? As logic of program is not language-dependent there should be a way to it the value of ans initially is zero and returning zero for any input

Answer 1

Just because the logic is not language-dependent doesn't mean that the implementation is also not language-dependent. Imagine implementing the logic in a purely functional language that has no mutable state - the logic would be still the same, but the implementation needs to be very different.

To solve this problem your recursive function needs to update two values (cnt and ans) which makes the problem a bit unwieldy for the usual style (return the result directly).

Instead of that I would implement this with a helper object:

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Traverser t = new Traverser();
        t.traverse(root, k);
        return t.ans;
    }

    static class Traverser {
        int cnt = 1;
        int ans = 0;
        void traverse(TreeNode root, int k) {
            if (root == null) return;

            traverse(root.left, k);
            if (cnt++ == k) {
                ans = root.val;
                return;
            }
            traverse(root.right, k);
        }
    }
}

Note that the Traverser.traverse() method neatly aligns with your traverse implementation - just the two parameters ans and cnt have been migrated into fields of the Traverser class.