Search in Tries
excerpt: This covers how to implement search in Tries.
The search method takes the key to search in the trie. It compares the target key with the key in a node, if it matches it returns the value of the node. If it does not match the node’s key value, the search continues in the child node. If the current node has no children, the target key is not in the trie, so the method returns null.
If the node has children, the method calculates the index of the target key’s child. If that child does not exist, the target key is not in the trie and null is returned. Finally if the target key’s child exists, recursive call is made for that child to find the target key.
Search Implementation


Traverse the trie from the root, till there are no characters left in key prefix or it is not possible to continue the path in the trie with the current key character. When we come to an end of the key prefix, we return true.