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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class TrieNode
  attr_accessor :end_of_word, :links

  def initialize()
    @links = {}
    @end_of_word = false
  end    
end

class Trie
  def initialize()
    @root = TrieNode.new
  end

  def search(word)
    node = @root
  
    for i in (0..word.size - 1)
      letter = word[i]
      if !node.links.key?(letter)
        return false
      end
      node = node.links[letter]
    end
  
    return node.end_of_word
  end
end

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.