java - DFS over string trie (prefix) -

i wrote following prefix trie:

class trienode {     char letter;     hashmap<character,trienode> children;     boolean fullword;      trienode(char letter) {         this.letter = letter;         children = new  hashmap<character, trienode>();         this.fullword = false;     } }  class tree{     static trienode createtree() {          return (new trienode('\0'));     }      static void insertword(trienode root, string word) {         int l = word.length();         char[] letters = word.tochararray();         trienode curnode = root;         (int = 0; < l; i++) {             if (!curnode.children.containskey(letters[i]))                 curnode.children.put(letters[i], new trienode(letters[i]));             curnode = curnode.children.get(letters[i]);         }         curnode.fullword = true;     } } 

i add dfs method in order find first node has more 1 child (so show me longest common prefix).

i wrote code:

static void dfs(trienode node) {     (trienode tn: node.children.values()){        dfs(tn);         if (node.children.size()>2)         system.out.println("found first vertex");     } } 

but doesn't work. doing wrong?

well, first need clarify longest common prefix here means longest common prefix of 2 or more strings in trie tree.

so, dfs method won't work because traverse whole tree , output "found first vertex" on visiting node children.size() > 2 (it should >=2 here)

what want here finding longest common prefix only. need information longest one. it's easy see in example above:

          root      --depth: 0            |                   --depth: 1            |            b        --depth: 2           / \          c   f      --depth: 3         /|\        d g k        --depth: 4             \              k      --depth: 5  

the longest common prefix node has children.size()>1 and has max depth. in case, it's node c

so here's 1 possible correct dfs:

static int max=-1; static trienode maxnode=null;  static void dfs(trienode node, int depth){     if(node.children.size()>1 && depth>max){         max=depth;         maxnode=node;     }     (trienode tn: node.children.values())         dfs(tn,depth+1); }  public static void test(){     trienode root = tree.createtree();     tree.insertword(root, "abcd");     tree.insertword(root, "abcg");     tree.insertword(root, "abckk");     tree.insertword(root, "abf");     dfs(root,0);     system.out.println("max node:"+maxnode.letter); } 

after running of dfs, maxnode hold node longest common prefix stops. it's node c in case.