This is my node and driver class. I need to find the smallest value on the left side of the tree.

import java.util.ArrayList;
import java.util.List;

public class NTreeNode<T> {
  public T value;
  public List<NTreeNode<T>> children;

  public NTreeNode(T val) {
    value = val;
    children = new ArrayList<NTreeNode<T>>();
  }

  public String toString() {
    return value + "@" + children;
  }

  public String toString(String indent) {
    String result = indent + value + "\n";
    for (NTreeNode<T> child : children) {
      result += child.toString(indent + "  ");
    }
    return result;
  }




  /** Helper method to make it easier to construct trees.
   *  The first data value is always the root value.
   *  The path values must give the index of each node in the path
   *  to the parent node of the next value you wish to insert.
   *  Parent nodes MUST appear in the list before their children.
   * @param paths The path to the parent of the next value.
   * @param data The value to insert into the tree.vv
   * @return NTreeNode<T> The root of the constructed tree.
   */
  public static <T extends Comparable<? super T>>
      NTreeNode<T> buildTree(List<String> paths, List<T> data) {
    // Sanity check inputs.
    if ((paths == null) || (data == null) ||
        (paths.size() != data.size()) || (paths.size() < 1)) {
      return null;
    }
    // Root node.
    NTreeNode<T> root = new NTreeNode<T>(data.get(0));
    // Remaining values.
    for (int pos = 1; pos < paths.size(); pos++) {
      NTreeNode<T> current = root;
      String path = paths.get(pos);
      // Find the parent node of the next value to be inserted.
      for (int step = 0; step < path.length(); step++) {
        current = current.children.get(Integer.parseInt(""+path.charAt(step)));
      }
      // Add the new node to the tree at the correct location.
      current.children.add(new NTreeNode<T>(data.get(pos)));
    }
    return root;
  }


  public static void main(String[] args) {
    ArrayList<String> paths = new ArrayList<String>();
    ArrayList<String> data = new ArrayList<String>();
    paths.add(""); data.add("root");
    paths.add(""); data.add("A");
    paths.add(""); data.add("B");
    paths.add(""); data.add("C");
    paths.add("0"); data.add("A-A");
    paths.add("1"); data.add("B-A");
    paths.add("1"); data.add("B-B");
    paths.add("1"); data.add("B-C");
    paths.add("2"); data.add("C-A");
    paths.add("00"); data.add("A-A-A");
    paths.add("10"); data.add("B-A-A");
    paths.add("11"); data.add("B-B-A");
    paths.add("12"); data.add("B-C-A");
    paths.add("100"); data.add("B-A-A-A");
    System.out.println(buildTree(paths, data).toString(""));
  }

}

what I've done so far is this, but it doesn't work.

public class TreeMinimum<T extends Comparable<? super T>> {
    public T findMin (NTreeNode<T> root) {
        int min = Integer.MAX_VALUE;

        
        if (root == null) 
            return null;
        else if (root.children == null)
            return root.value;
            
        for (int i=0; i<root.children.size()-1;i++) {    
            while (root.children != null) {
                root = root.children.get(i);
                if (root.value < min)
                    min = root.value;
            }
        }
        
        return min;
    }
}

What doesn't work about the code? What value does it return in error?

I don't see any debug code to help you see how the algorithm is working. Try adding some println() to see what the code is doing.

It seems strange to me that you're trying to find the smallest value on an unsorted tree. If this is an assignment, does it say that you're not allowed to sort the tree?

If you can rebuild the tree in the correct order, then you just loop continuously looking at the left-most child until you reach a leaf node, and that's your minimum node right there.

Otherwise, in an unsorted tree the only solution would be to look at every single node and identify which is the smallest (a breadth-first traversal would be the quickest way to do that).

Edit: Just realised that this thread has already been solved. Didn't notice that before posting.

Edited 6 Years Ago by leiger: n/a

This question has already been answered. Start a new discussion instead.