Looping through all values in a BST to get value to use in another BST

[softwareTurtle]

Homework Statement

Finish the implementation of buildIndex. You have access to the parameter BST<Path, Ngram[]> files, which contains the 5-grams of each file, as described above. The method should return a BST containing all 5-grams containing in all input files; the value associated with a 5-gram should be the list of files containing that 5-gram (in any order).
Note that the Ngram class already implements the Comparable<Ngram> interface, so you do not need to implement any extra code to be able to compare 5-grams. Also, BST.java is already implemented for you – you do not have to create your own binary search tree implementation.

Relevant Equations

for(ArrayList<Path> paths: paths) {
for(Ngram ngrams: files.keys()) {
index.put(ngrams, paths);
}
}

I have a Algorithms and data structure lab that I'm really struggling with. I do not understand how I should iterate over all values to create the new index.

    static BST<Ngram, ArrayList<Path>> buildIndex(BST<Path, Ngram[]> files) {
      BST<Ngram, ArrayList<Path>> index = new BST<Ngram, ArrayList<Path>>();
     
      return index;
    }

 

[Valkarie]

You can iterate over all the values in the BST by using a pre-order traversal. A pre-order traversal starts at the root node and visits each of the left subtree nodes before visiting the right subtree nodes. For each node, you can get the key (the Ngram) and the value (the ArrayList of Paths). You can then check if the Ngram is already present in the index BST. If it is not, you can create a new entry with the Ngram as the key and an empty ArrayList as the value. Otherwise, you can retrieve the existing ArrayList and add the Path from the files BST to it. Once you have iterated over all the nodes in the files BST, you will have a fully populated index BST. Here is some sample code that implements this algorithm:static BST<Ngram, ArrayList<Path>> buildIndex(BST<Path, Ngram[]> files) { BST<Ngram, ArrayList<Path>> index = new BST<Ngram, ArrayList<Path>>(); // perform a pre-order traversal of the files BST Stack<BSTNode<Path, Ngram[]>> stack = new Stack<BSTNode<Path, Ngram[]>>(); stack.push(files.getRoot()); while (!stack.isEmpty()) { BSTNode<Path, Ngram[]> node = stack.pop(); Path path = node.getKey(); Ngram[] ngrams = node.getValue(); for (Ngram ngram : ngrams) { // check if the ngram already exists in the index ArrayList<Path> paths = index.get(ngram); if (paths == null) { // ngram does not exist, create a new entry paths = new ArrayList<Path>(); index.put(ngram, paths); } // add the path to the list of paths paths.add(path); } // push the left child onto the stack if (node.getLeft() != null) { stack.push(node.getLeft()); }