Implement Trie (Prefix Tree)

A Trie, also known as a “prefix tree,” is a tree-like data structure used for storing a dynamic set of strings. Tries are useful for operations like searching, inserting, and deleting strings. One key advantage is that Tries can quickly find all keys with a common prefix, making them useful for auto-complete features and dictionaries.

In a Trie, each node represents a single character of a string, and each path from the root to a node represents a prefix of strings in the set. The leaf nodes correspond to complete strings.

Example Code in Java

 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
class TrieNode {
    boolean isEnd;
    TrieNode[] children = new TrieNode[26];
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new TrieNode();
            }
            node = node.children[c - 'a'];
        }
        node.isEnd = true;
    }
    
    // Other methods like search, delete
}

Example Code in C++

 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
29
30
31
#include <iostream>
#include <vector>

struct TrieNode {
    bool isEnd;
    std::vector<TrieNode*> children;

    TrieNode() : isEnd(false), children(26, nullptr) {}
};

class Trie {
public:
    TrieNode* root;

    Trie() {
        root = new TrieNode();
    }

    void insert(std::string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children[c - 'a']) {
                node->children[c - 'a'] = new TrieNode();
            }
            node = node->children[c - 'a'];
        }
        node->isEnd = true;
    }
    
    // Other methods like search, delete
};

Example Code in Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class TrieNode:
    def __init__(self):
        self.isEnd = False
        self.children = {}

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.isEnd = True
    
    # Other methods like search, delete

With this implementation, you can perform various string operations efficiently. Each operation like insert, search, and delete can be done in ( O(n) ) time complexity, where ( n ) is the length of the word.

A Trie is a specialized tree structure where each node represents a part of a string. It’s used to efficiently store a large set of strings. Let’s implement the Trie class as described:

Initialization (__init__ method): Create a root node with an empty dictionary to store children nodes and a boolean flag to mark the end of a word.
Insertion (insert method): Add a word to the Trie, starting from the root and following the characters of the word.
Search (search method): Check if a word exists in the Trie.
Prefix Search (startsWith method): Check if there’s any word in the Trie that starts with a given prefix.

Here’s the code implementing the Trie class:

 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
29
30
31
class Trie:

    def __init__(self):
        self.root = {'*': False} # '*' marks the end of a word

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            # Add a new node if character not in Trie
            if char not in node:
                node[char] = {'*': False}
            node = node[char]
        node['*'] = True # Mark the end of the word

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            # If character not found, return False
            if char not in node:
                return False
            node = node[char]
        return node['*'] # Return True if it's the end of a word

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            # If character not found, return False
            if char not in node:
                return False
            node = node[char]
        return True # Return True if prefix found

Explanation:

The root node is a dictionary, and each character in the strings is a key in the dictionary. The value associated with each key is another dictionary, representing the child nodes.
The special key '*' is used to mark the end of a word.
The insert method builds the Trie by adding nodes for each character in the word.
The search method traverses the Trie following the characters of the word and checks if the end of the word is reached.
The startsWith method is similar to search but returns True if the prefix is found, regardless of whether it’s the end of a word.

The operations of insert, search, and startsWith have a time complexity of O(m), where m is the length of the word or prefix being processed. The space complexity of the Trie is O(n), where n is the total number of characters in all the words stored in the Trie.

Applications

Autocomplete
Spell checker
IP routing (longest prefix matching)

Also known as prefix tree. We can efficiently match prefixes.

Why trie?

Uses less space than hashtable

How can we implement the insert?
- How to create root?
  - links size is 26 (will hold the characters)
- Root does not store anything
Create empty links and define a end_of_word boolean In the constructor
Insert operation: Traverse the characters in the word Pick the first character Check if it is already in the root in the links held by the root If it is not: Create a new trie node instance and set it’s character value to the first letter Outside the loop, mark the end_of_word = true for the last character

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class TrieNode
    attr_accessor :end_of_word, :links

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

end

class Trie

=begin
    Initialize your data structure here.
=end
    def initialize()
        @root = TrieNode.new
    end


=begin
    Inserts a word into the trie.
    :type word: String
    :rtype: Void
=end
    def insert(word)
        node = @root
        for i in (0..word.size - 1)
            letter = word[i]
            if !node.links.key?(letter)
                node.links[letter] = TrieNode.new
            end
            node = node.links[letter]
        end
        node.end_of_word = true
    end


=begin
    Returns if the word is in the trie.
    :type word: String
    :rtype: Boolean
=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


=begin
    Returns if there is any word in the trie that starts with the given prefix.
    :type prefix: String
    :rtype: Boolean
=end
    def starts_with(prefix)
        node = @root
        for i in (0..prefix.size - 1)
           letter = prefix[i]
            if !node.links.key?(letter)
                return false
            end
            node = node.links[letter]
        end
        
        return true
    end
end

# Your Trie object will be instantiated and called as such:
# obj = Trie.new()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.starts_with(prefix)