Finding the minimum value of a 2-3-4 tree

Question

First off, this question isn't homework. I'm currently reading the book "Data Structures and Algorithms 2nd Edition" by Robert Lafore. In chapter 10, we learned about 2-3-4 trees and are then asked to write a method to find the minimum value in said tree.

From a concept standpoint, I understand where the minimum value is. It is just the left most data item in a leaf.

From a programming standpoint, I'm a little confused on how to implement a method to find this data item. I have a boolean that can tell if the node is a leaf. So what I originally did was this:

  public long minValue() {
   Node curNode = root; // current node = root
   long min = curNode.getMin();
   while(!curNode.isLeaf()) { // while current node is NOT a leaf
       curNode = getNextChild(curNode, min);
   } // end while
   return min;
} // end minValue()

What this does (at least what I think it should do, is create a curNode that starts at the root node. Then create a min value that stores curNode.getMin. getMin() just gets the value at the array at index 0 (where the lowest value should be held). Then, while the current node is not a leaf, we should traverse to the next child from the minimum point. Once the current node is a leaf, it should return the minimum value.

This doesn't work though. Does anyone have an idea on how to implement this? Hints or suggestions or anything else?

Edit: To see each of the classes and how they interact, here are links to each separate class. I put the minimum value method in my Tree234 class

DataItem, Node, Tree234, and where the program is run, Tree234App

Sorry, just meant it stores that value when curNode.getMin() is called. It's just the left-most data item (which should contain the minimum value in that node). — Alex, Jul 29 '14 at 01:27
@PM77-1 It's more of an exercise than anything. You're just supposed to insert items into the 2-3-4 tree, then output the minimum value from that tree. — Alex, Jul 29 '14 at 01:28
So your code needs to build the tree and then use it to output the minimum? — PM 77-1, Jul 29 '14 at 01:37
@PM77-1 I believe so. I added the code for everything. But yeah, basically you would call insert() on a bunch of values in main(). Then you would call findMinValue() or something and it would output the minimum value for you. — Alex, Jul 29 '14 at 01:43

score 3 · Accepted Answer · edited Mar 20 '17 at 10:29

First, for better help sooner, post an SSCCE that gives us a minimal implementation of your entire program - something we can c/p into our own IDE and run ourselves to see what's going on. It's hard to tell why "this doesn't work" when we only see this bit of your code.

Second, you need to elaborate on what "this isn't working" means - i.e. tell us exactly what it's doing or not doing that is unexpected. In lieu of you having done so, how could we tell you with any degree of certainty why it's doing that.

However, one thing jumps out: You're instantiating min as the smallest (direct) child of the root node, then (presumably) iterating through the tree to find the left-most element in it, but then you're returning the same min value you created initially. In other words, while your iterative routine might be doing exactly what you want it to, you're not doing anything to the return value as a result of it.

I suspect you need to do something like:

  public long minValue() {
      Node curNode = root;
      long min = curNode.getMin();
      while(!curNode.isLeaf()) { // 
           curNode = getNextChild(curNode, min); //it's not immediately clear what min is doing here 
       } 
       //curNode is now the leftmost non-leaf element in the tree
       min = curNode.getMin();
       return min;

Note that the only change I made was inserting the line above the return statement, which reassigns min to the minimum value attached to the left-most element in the tree.

Thanks for the link to that. For the second point, wow, I really did not think my question through. The problem was, it would return the first (smallest) node in the root, and would not progress further. Not sure why I didn't realize I needed to update my min value.. but yep, this worked. Thanks for the help! — Alex, Jul 29 '14 at 01:58

score 0 · Answer 2 · answered Apr 07 '16 at 09:35

For more efficiency, note that you don't need to call getNextChild(curNode, min), since the items in node are always sorted in ascending order in 2-3-4 tree and the smallest item is always at index 0. Declaration of min is also not necessary at start. So your program could be like this:

public long minValue() {
    Node curNode = root;
    while (!curNode.isLeaf()) {
        curNode = curNode.getChild(0);
    }
    return curNode.getMin();
}

Finding the minimum value of a 2-3-4 tree

2 Answers2