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

CodePudding user response：

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.

CodePudding user response：

High-level

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

Which may be helpful for debugging.