Question

Root is a trie that has characters for values. When traversed it spells words by formin strings.

I'm trying to make findNode such that it will return the node at which we start collecting candidates for words that start with a specific prefix.

How do I code this method traversing depth-first?

my code:

private static TreeNode<Character> findNode(TreeNode<Character> root, String prefix, int index){

Stack <TreeNode<Character>> s = new Stack<>();

s.push(root);

for(TreeNode<Character> child : root.getChildren()){
while(index <= prefix.length()-1){
if(prefix.charAt(index) == child.getValue()){
index++;
findNode(child, prefix, index);
if(prefix.charAt(index) != child.getValue()){
return child;  
}
}
}
}

}

Answer 1

Assuming standard functions such as getChildren() to be present in your implementation of the Trie Class and index is passed as 0 in the beginning.

There is no requirement of a stack in the above code. Since , we want to reach to that node from which , we can start collecting candidates for making new words having that prefix. It actually means traversing the trie to reach to the last letter of the prefix. When we reach and return the last letter of the prefix , we can form all possibe words from there on. Hence , we must return the node with last letter of the prefix starting with the root.

There is a mistake in declaring the Base cases and making the code more efficient . Here is how you can do it in a better way.

private static TreeNode<Character> findNode(TreeNode<Character> root, String prefix, int index)
{
 /* If the root is NULL and has no characters */
 if(root==NULL)
    return root;
 /* Get all its children */
 for(TreeNode<Character> child : root.getChildren())
 {
         /* If the character of root's children matches with Prefix[index] */
         if(prefix.charAt(index) == child.getValue())
         {
            /*Increase the index and search for next character of prefix */
            index++;
            /*If entire prefix is found , return the current root (the last element)*/
            if(index == prefix.length())
                return child;
            /* Other wise , simply called the function recursively */ 
            else 
                return findNode(child, prefix, index);
         }
  }
  /* If no children of root has Prefix[index] character , that means it is not possible to make prefix*/
  return NULL;
}