Well, first we need to clarify that longest common prefix here means the longest common prefix of any two or more strings in the trie tree.
So, your DFS method won't work well because it simply traverse the whole tree and will output "found the first vertex" on visiting any node whose children.size() > 2 (It should be >=2 here)
What we want here is finding the longest common prefix only. So we need some extra information about which is the longest one. It's easy to see that in my example above:
root --depth: 0
|
a --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 this case, it's node c
So here's one 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;
}
for (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, the maxNode will hold the node which longest common prefix stops. it's node c in this case.