I am struggling to figure out how to make an inverted index from an index which stores nodes as binary search trees containing a linked list of strings. ie: Root node Jessie points to a list of the things she ate (apple, banana, pear):

here is the code for the implementation of index: (ie the index class that controls the code in the program)

public class Index { // Nodes for linked lists of values private class Node { String value; Node next; public Node(String v) { value = v; } } // nodes for the binary tree private class TreeNode { String key; Node values; TreeNode left; TreeNode right; public TreeNode(String s) { key = s; } } private TreeNode root = null; public String toString(TreeNode t) { //toString of TreeNode return t.key + ":[" + toString(t.values); //return string key + :[ and then the values from the node as defined in earlier to string } private String toString(Node t) { //Makes node a string if (t == null) { //if Node empty just return end bracket return "]"; } else if (t.next == null) { //if last pointer return value + end bracket return t.value + "]"; } else { return t.value + ";" + toString(t.next); //else, return the value + ; + toString of treeNode value } } 

I then have a bunch of code creating it, which I have tested rigorously and works. Now, i need to use this to make the inverted index from this treeNode, wherein the values are the key and the key is the values. Ex, if the jessica pointed to values : banana, apple, and the key Jane pointed to values: apple, hamburger, in the new inverted index there would be a key apple that would point to values: jessica, jane. Since they both ate apples.

Here is my code for it, and the tests I run and how they turn out.

//methods to build inverted index public Index getInvertedIndex() { return InvertedHelper(root); } private Index InvertedHelper(TreeNode t) { Index NewTable = new Index(); //create empty index IndexCreator(NewTable, t); //initialize values in new index using index creator return NewTable; } private void IndexCreator(Index A, TreeNode t) { if (t == null) {}//if empty, do nothing else{ //traverse/put in values while (t.values != null && t.values.value != null) {//while values list and values in value list are not null A.insert(t.values.value, t.key); //insert in reverse order( with value in values for key, and key for values) t.values = t.values.next; //move values up } } //traverse/ keys if(t != null){ IndexCreator(A, t.left); IndexCreator(A, t.right);}} 

Here is the testing code (I'm only including the initializer index and the code that tests for the inverted index, obviously in other tests these get changed a bit so don't worry about that just look at what SHOULD be printed out)

Index D = new Index(); String[][] V = { {"Coke", "Salad", "Pasta" }, {"Pepsi", "Salad", "Chicken", "Salad" }, // Node duplicate value  {"Chicken", "Pasta"} }; D.insert("Ringo", V[0]); D.insert("John", V[1]); D.insert("George", V[2]); D.insert("George", "Pasta"); // duplicate, should not be inserted D.insert("George", "Milk"); D.insert("Wayne"); D.insert("Paul"); D.insert("Paul", "Pasta"); D.insert("Paul", "Beef"); D.insert("Paul", "Coke"); D.insert("Paul", "Pasta"); // duplicates, should not be inserted D.insert("Paul"); D.insert("Wayne"); System.out.println(" Building Inverted Index.... "); Index InvD = D.getInvertedIndex(); System.out.println("[10] Printing tree, should be: "); System.out.println("\tSalad:[John] " + "Pepsi:[John] " + "\t\tPasta:[George;Paul] " + "\t\t\tMilk:[George] " + "\t\t\t\tCoke:[Paul] " + "\tChicken:[John;George] " + "\t\tBeef:[Paul] "); InvD.printTree(); System.out.println(" [12]: Testing size, should be: 7"); System.out.println(InvD.size()); System.out.println(" [13]: Testing height, should be: 4"); System.out.println(InvD.height()); System.out.println(" [14]: Testing getValues, should be: [George;Paul]"); System.out.println(InvD.getValues("Pasta")); System.out.println(" [15]: Testing getValues, should be: null"); System.out.println(InvD.getValues("Pork")); 

Now here is what my code prints

Building Inverted Index....

[10] Printing tree, should be:

Salad:[John]

Pepsi:[John]

Pasta:[George;Paul]

Milk:[George]

Coke:[Paul]

Chicken:[John;George]

Beef:[Paul]

Salad:[Salad]

Pepsi:[John]

Pasta:[Pasta;Paul]

Milk:[George]

Coke:[Paul]

Chicken:[John;George]

Beef:[Paul]

[12]: Testing size, should be:

7

7

[13]: Testing height, should be:

4

4

[14]: Testing getValues, should be:

[George;Paul]

[Pasta;Paul]

[15]: Testing getValues, should be:

As you can see, it is printing pasta and salad where it should not be printed, and I have no clue why! If you could give me a hint or point me in the right direction it would make a world of help! Thank you!