my method is not returning the minimum difference of nodes in a bst

Question

I'm not sure why its not returning the minimum difference that can be found in the binary search tree. I cant debug nor use tester which has made it more difficult to find the issue.

Instrcutions:

Implement a method called getMinimumDifference() that takes in as parameter the root of a Binary Search Tree and returns an integer denoting the minimum absolute difference of any two distinct nodes within the Binary Search Tree.

Assumptions:

The node values in the binary search tree are greater than or equal to zero. All node values in the binary search tree are unique. The method will never receive the root of a tree that less than 2 nodes.

tree: [4,2,6,1,3] 

            4
      2____||____6
 1___||___3

expected output: 1

public static int getMinimumDifference(BTNode<Integer, Integer> root) {     
        int minHolder = 9;
        BTNode<Integer, Integer> newNode = null;
        recgmd(minHolder, root, newNode);
        return minHolder;
    }
    public static void recgmd(int minHolder,BTNode<Integer, Integer> currentNode, BTNode<Integer, Integer> prevNode) {
        if(currentNode == null) {
            return;
        }
        recgmd(minHolder, currentNode.getLeftChild(), prevNode);
        if(prevNode != null){
            if(currentNode.getValue() - prevNode.getValue() <= minHolder) {
                minHolder = currentNode.getValue() - prevNode.getValue();
            }
        }
        prevNode = currentNode;
        recgmd(minHolder, currentNode.getRightChild(), prevNode);
    }

Description of how my code works:

Order: in-order
Why? To be able to compare between the previous node and the current one since they will be ascending order

>getMinimumDifference<
<Parameter>[root]

-[minHolder] Created variable that will be returned with the minimum difference found in BST.
-[newNode] Created node(will function as a prevNode) that will be compared with the current node on the helper method.
-Calls the helper, passing as parameters:[minHolder], [currentNode] and [prevNode].

>recgmd<
<Parameter>[minHolder] Variable that will be returned with the minimum difference found in BST.
<Parameter>[currentNode] Self-explanatory.
<Parameter>[prevNode] Self-explanatory.

-if the [currentNode] is null, returns
-recursive call to left child
-if its the first round(where [prevNode] is still null, skips)
--Otherwise, we check if the difference between the value of the [currentNode](which will always be greater than the later) and the [prevNode] is less than the value contained in [minHolder]
---if it is, the difference is saved in [minHolder]
----Otherwise, it continues
-[prevNode] is updated
-recursive call to left child

Answer 1

You have to made the calculation for min value for every step:

public static void recgmd(int minHolder,BTNode<Integer, Integer> currentNode, BTNode<Integer, Integer> prevNode) {
    if(currentNode == null) {
        return;
    }
    
    if(prevNode != null){
        if(currentNode.getValue() - prevNode.getValue() <= minHolder) {
            minHolder = currentNode.getValue() - prevNode.getValue();
        }
    }
    prevNode = currentNode;
    recgmd(minHolder, currentNode.getLeftChild(), prevNode);
    recgmd(minHolder, currentNode.getRightChild(), prevNode);
}

Note: prevNode should have right value for every parentNode, not only for rightNode 's parent.

Answer 2

High-level

Assuming another way to look at this is, given one int-labelled node in a connected acyclic graph, with DFS or BFS with an accumulator, return the value of the edge that has the least absolute difference between two nodes at it's endpoints. There will always be at least one edge, all nodes are non-negative, and nodes are unique.

The non-negative means we can always store it in an int. The nodes are unique means the difference value will be positive.

Structure of class

int getMinimumDifference does not fit with generics in BTNode<Integer, Integer>. From what you have posted, there should be no need for generics. The class BTNode data should have an int for the label and two BTNode for the children. If you aren't changing them, you might label them final.

Within the class, it's easiest if you have public int getMinimumDifference(). This receives this as a BTNode, so one could do int diff = root.getMinimumDifference().

There are lots of ways to do this, you might call private int recgmd(), a recursive helper method that returns the minimum out of all the edges in the sub-tree rooted at this. This may return the minimum of Integer.MAX_VALUE, |value - left.value|, left.recgmd(), |value - right.value|, and right.recgmd(), if the individual values exist.

Verify constraints

One could check that the constrains are followed. In programming with assertions it says "Do not use assertions for argument checking in public methods." I would use an unchecked exception in getMinimumDifference, before handing it off to recgmd.

        if(left == null && right == null)
            throw new IllegalArgumentException("one node");

The uniqueness guarantee means one might also check if it's greater than zero before returning it.

In recgmd, one might test that the non-negative constraint is held.

        if(value < 0) throw new IllegalArgumentException("negative node");

Debug

    public String toString() {
        StringBuilder sb = new StringBuilder(80);
        /* Not guaranteed to be unique, but, for our purposes, it's unlikely to
         cause a collision. See, <https://stackoverflow.com/q/909843/2472827>. */
        sb.append("\tnode").append(System.identityHashCode(this))
            .append(" [label=\"").append(value).append("\"];\n");
        if(left != null) sb.append("\tnode")
            .append(System.identityHashCode(this)).append(" -> node")
            .append(System.identityHashCode(left)).append(";\n").append(left);
        if(right != null) sb.append("\tnode")
            .append(System.identityHashCode(this)).append(" -> node")
            .append(System.identityHashCode(right)).append(";\n").append(right);
        return sb + "";
    }

    public static void main(String[] args) {
        BTNode root = new BTNode(4, new BTNode(2, new BTNode(1),
            new BTNode(3)), new BTNode(6));
        System.out.printf("digraph {\n\tgraph [truecolor=true, bgcolor=transparent, fontname=modern];\n\tnode [shape=plaintext, fontname=modern];\n%s}\n", root);
    }

Running java BTNode > tree.gv and opening it with Graphviz gives,

Which may be helpful for debugging.

Binary Search Tree vs Binary Search

If one has a sorted array, you can perform a binary search without a tree structure. See Difference between binary search and binary search tree? In this case, a tree could be viewed as implicit, defined, for example in [int left, int right).