Finding kth min/max in BST

Question

Please critique my code. (Specifically, I'm not sure if my use of member variables is appropriate.)

Here is the main structure of my BST class:

public class bst {

    private Node root;

    public class Node {

        int data;
        Node left, right;

        private Node(int data) {
            this.data = data;
            left = null;
            right = null;
        }
    }
}

The bst class contains the following methods to find kth max/min element

private static int min;
private static int max;
private static int target;
private static boolean isFound;
private static int level;
private static int nodes;

public int KthMin(int k) {

    //initializing helper variables
    target = k;
    isFound = false;
    min = 0;
    level = 1;
    nodes = 0;

    KthMinHelper(root);

    if (target > nodes) {
        throw new IndexOutOfBoundsException();
    }

    return min;
}

private void KthMinHelper(Node n) {

    if (isFound) {
        return;
    }

    nodes++;

    if (n.left != null) {
        KthMinHelper(n.left);
    }

    if (level == target) {
        min = n.data;
        isFound = true;
    }
    level++;

    if (n.right != null) {
        KthMinHelper(n.right);
    }
}

public int KthMax(int k) {

    //initializing helper variables
    target = k;
    max = 0;
    isFound = false;
    level = 1;
    nodes = 0;

    KthMaxHelper(root);

    if (target > nodes) {
        throw new IndexOutOfBoundsException();
    }

    return max;
}

private void KthMaxHelper(Node n) {

    if (isFound) {
        return;
    }

    nodes++;

    if (n.right != null) {
        KthMaxHelper(n.right);
    }

    if (level == target) {
        max = n.data;
        isFound = true;
    }
    level++;

    if (n.left != null) {
        KthMaxHelper(n.left);
    }

}

This is how my test driver looks like:

 public static void main(String[] args) {
    bst tree = new bst();
    int[] a = {11, 5, 2, 9, 7, 6, 3};

    for (Integer n : a) {
        tree.insert(n);
    }

    System.out.println("\nkth min:" + tree.KthMin(3));
    System.out.println("kth max:" + tree.KthMax(2));
}

Answer 1

First of all, do not use static variables to store anything that is not directly singleton related. All your variables - min, max, target, isFound, level, nodes - should be handed around in the call, not stored in class static variable. This not only makes the code utterly unreadable, but it will not be possible to make concurrent calls on the BST, even though search should be thread safe operation.

Namely: target does not need to exist at all and can be replaced by level only, max|min as return value respectively or in some other way, level can be decremented with every found minimum to leave out target, nodes is really clunky way to mark - not found, simply put, if there is k elements in the BST, trere must be k-th minimum or maximum, so before even going into recursion, you can compare target with number of elements in the tree (updated in class variable on every insert/remove)

---

Adding suffix "Helper" to your methods is redundant with them being private, and it actually makes them bit more obscured.

---

Avoid using of one letter variable names. Exception would be some math problem where these variables are commented right before use, or indexes in loops.

---

It is common convention to have names of methods start with lower case letter, while upper case is for classes. this way, you should have kthMax. For class Bst or better, since it is abbreviation, BST or for clarity, since BST can be anything, BinarySearchTree.

---

It would be really complicated to work around level and isFound being returned. In this case, search state class seems to be a good idea.

private class SearchState{
    public int level;
    public boolean found = false;
    public final boolean isMin;
    public int value = 0;

    public SearchState(boolean isMin, int level){
        this.isMin = isMin;
        this.level = level;
    }

    public Node first(Node in){
        return isMin?in.left:in.right;
    }

    public Node last(Node in){
        return isMin?in.right:in.left;
    }

    public void check(Node in){
        if (this.level == 0) {
            this.value = in.data;
            this.found = true;
        }
        this.level--;
    }
}

As you can see, it contains all necessary information and methods for distinguishing between min and max search.

Unified method for search of kth number would be then

private void kthRecursion(Node node, SearchState state) {
    if (state.found || node==null) {
        return;
    }

    kthRecursion(state.first(node), state);

    state.check(node);

    kthRecursion(state.last(node), state);
}

and its use

public int kthMin(int k){
    return kthInit(k, true);
}

public int kthMax(int k){
    return kthInit(k, false);
}

private int kthInit(int k, boolean isMin){
    if(k>size || k<=0){
        throw new Exception("Invalid argument "+k+"!");
    }

    SearchState state = new SearchState(isMin, k-1);
    kthNumber(root, state);
    return state.value;
}

Do not know whether this code works, since I do not have rest of your class, but it should work. Please let me know if it does not along with remaining parts of your class so I can fix it.

Hope it helps, regards.