String Array (Tree)

Question

Suppose we have 5 String arrays:

String[] array1 = {"hello", "i", "cat"};
String[] array2 = {"hello", "i", "am"};
String[] array3 = {"hello", "James"};'
String[] array4 = {"hello", "i", "bob"};
String[] array5 = {"hello", "mike", "wasup"};

How would I create a tree where "hello" is always the root, and the second element is the child of the root and and the other elements become the children of the sub root. (each node could have 0-n node children)

An an example:

           hello
        /   \    \
      i    james   mike
    / \ \           /
  cat  am bob    wasup

The diagram above is a type of tree I want. Please don't write any code. I want to understand the concept. Explain your approach as a programmer.

Create a tree, iterate through each array, walk the nodes and create new ones as necessary. — shmosel, Nov 09 '17 at 23:07
I was thinking the same, however how would I reference different nodes? I have learned binary tree where there are 2 references, left and right, but in this case I can't understand what would get the job done. — Armin, Nov 09 '17 at 23:13

score 1 · Answer 1 · answered Nov 09 '17 at 23:08

1

I would use a tree structure then I would iterate on each array filling the tree. Root = hello

Then for each wore of the array, check the leaves for this word

if it does not contain your word, then create a new leaf with key = current word

Then I go down in the tree and move forward in the array

Do this till the end of your array

Java tree data-structure?

answered Nov 09 '17 at 23:08

Juli3n

221
1
5

Correct me if i'm wrong, for a binary tree you would have a left and right reference, for this, since each node could have 0-n nodes how would you reference different nodes? – Armin Nov 09 '17 at 23:11

score 1 · Answer 2 · answered Nov 09 '17 at 23:19

1

Define a Node class that is Composite. Create Map where the key is your Strings in those arrays and value is the Node. Iterate over the array check if there is an already created Node for that value, if not create one. Then check the previous value and add your Node to that values associated Node.

answered Nov 09 '17 at 23:19

tsolakp

5,858
1
22
28

Haven't heard of Composite but I would definitely take a look at it. – Armin Nov 09 '17 at 23:21

score 1 · Accepted Answer · answered Nov 09 '17 at 23:22

It is a tree of which words may immediately follow a given word.

As such there should be an artifical root, as there could have been sentences with an other word than "hello."

Have all those sentences (array1, ...) themselves put in an array (or collection or database). So one can walk over them; can think of them as iterable.

Have a partial tree, initially empty, only containing the ROOT.

Then loop till all words are in the tree, looking for new words to add to allready present words. For every sentence put the first word under the root (ROOT is already present). For every other word, if the previous word is in the tree, put that word under the previous tree.

As you see, a naive approach (following the above) would on stable fixed data would need to skip much. One can of course have a mapping of word to its a tree node holding all its successors, and then the algorithm becomes quite simple.

I believe my lack of understanding English is the issue here. Thanks for the suggestion. — Armin, Nov 09 '17 at 23:29

String Array (Tree)

3 Answers3