4
\$\begingroup\$

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));
}
\$\endgroup\$
2
  • \$\begingroup\$ What's the use for this code, btw? If you want to find the \$k\$th min or max, there are much faster and simpler ways to do it. Quickselect is the obvious one, but you would likely be fine just sorting the array and taking the \$k\$th element. It's fine if this is just an exercise, though. \$\endgroup\$
    – Veedrac
    Jun 6 '15 at 2:35
  • \$\begingroup\$ @veedrac Yeah it was just a simple exercise. I'm just curious about my way of coding and if it could be improved. \$\endgroup\$
    – Devin
    Jun 6 '15 at 5:57
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Thank you very much for the detailed insights! This is what I was looking for. On a separate note, where can I learn such good practices? Any books/sites? \$\endgroup\$
    – Devin
    Jun 8 '15 at 10:28
  • 1
    \$\begingroup\$ I cant exactly forward you to anything in particular, unfortunately. I learned by reading a lot of code, by doing a lot of mistakes and writing even more code. Cooperating with people definitely makes a difference, so discuss code with your friends, coworkers, teachers, look into it and try to figure out better solutions. It is all about experience, since there simply is not one correct general solution. Good starting point for java programming conventions would be oracle. \$\endgroup\$ Jun 9 '15 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.