Trie Implementation
Tree Node has three attributes:
- Character
- boolean to check isLeaf
- children map
Insert Algorithm
- Take root children
- Iterate all characters of given string
- Set current_character = string.charAt(i)
- If current_character not exist in children map then
- Create a trie node for current_character and add to children map
- Get trieNode from children map for current_character
- If current_character is last character in given string then
- Set trieNode.isLeaf = true
- Set children = trieNode.children
Search Node Algorithm
- Get children of root
- Set trieNode = null
- Iterate all characters of given string
- Set current_character = string.charAt(i)
- If current_character not exist in children map then
- return null
- Else
- Set trieNode = children.get(current_character)
- Set children = trieNode.children
- Return trieNode
Latest Source Code:
Github: Trie.java
Output:
Is prefix "hrishi" exist? true Is "hrishik" exist? false Is "hrishikesh" exist? true Is "kumar" exist? false