Trie Data Structure

To construct a trie data structure, we will need to create two classes: Trie and TrieNode.

The TrieNode class represents a single node in the trie, and it contains an array of TrieNode objects called links to represent the next possible characters in the trie. Each TrieNode also has a boolean property isEnd to mark the end of a word.

Here is an example implementation of the TrieNode class in Java:

public class TrieNode {
    private TrieNode[] links;
    private boolean isEnd;

    public TrieNode() {
        links = new TrieNode[26];
    }

    public boolean containsKey(char ch) {
        return links[ch - 'a'] != null;
    }

    public TrieNode get(char ch) {
        return links[ch - 'a'];
    }

    public void put(char ch, TrieNode node) {
        links[ch - 'a'] = node;
    }

    public boolean isEnd() {
        return isEnd;
    }

    public void setEnd() {
        isEnd = true;
    }
}

The Trie class represents the trie itself and provides methods to insert a word, search for a word, and check if a word starts with a given prefix.

Here is an example implementation of the Trie class in Java:

public class Trie {
    private TrieNode root;

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

    public void insert(String word) {
        TrieNode current = root;

        for (char ch : word.toCharArray()) {
            if (!current.containsKey(ch)) {
                current.put(ch, new TrieNode());
            }

            current = current.get(ch);
        }

        current.setEnd();
    }

    public boolean search(String word) {
        TrieNode current = searchPrefix(word);

        return current != null && current.isEnd();
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private TrieNode searchPrefix(String prefix) {
        TrieNode current = root;

        for (char ch : prefix.toCharArray()) {
            if (!current.containsKey(ch)) {
                return null;
            }

            current = current.get(ch);
        }

        return current;
    }
}

```java
public class Trie {
    private TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode current = root;
        
        for (char ch : word.toCharArray()) {
            if (!current.containsKey(ch)) {
                current.put(ch, new TrieNode());
            }
            
            current = current.get(ch);
        }
        
        current.setEnd();
    }
    
    public boolean search(String word) {
        TrieNode current = searchPrefix(word);
        
        return current != null && current.isEnd();
    }
    
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }
    
    private TrieNode searchPrefix(String prefix) {
        TrieNode current = root;
        
        for (char ch : prefix.toCharArray()) {
            if (!current.containsKey(ch)) {
                return null;
            }
            
            current = current.get(ch);
        }
        
        return current;
    }
}

public class TrieNode {
    private TrieNode[] links;
    private boolean isEnd;
    
    public TrieNode() {
        links = new TrieNode[26];
    }
    
    public boolean containsKey(char ch) {
        return links[ch - 'a'] != null;
    }
    
    public TrieNode get(char ch) {
        return links[ch - 'a'];
    }
    
    public void put(char ch, TrieNode node) {
        links[ch - 'a'] = node;
    }
    
    public boolean isEnd() {
        return isEnd;
    }
    
    public void setEnd() {
        isEnd = true;
    }
}
```

In a trie data structure, each node contains links to the next possible characters in the trie.

To insert a new word into a trie, we can use the following steps:

1. Start from the root node and initialize a pointer current to track the current node.
2. Iterate through each character in the word.
3. Check if the current node contains a link for the character. If not, create a new node and add the character as a link.
4. Update the current pointer to the newly created node.
5. Repeat steps 3-4 for all characters in the word.
6. After iterating through all characters, mark the current node as the end of a word.

Here is an example implementation of the insert method in the Trie class:

public void insert(String word) {
    TrieNode current = root;

    for (int i = 0; i < word.length(); i++) {
        char ch = word.charAt(i);

        if (!current.containsKey(ch)) {
            current.put(ch, new TrieNode());
        }

        current = current.get(ch);
    }

    current.setEnd();
}

```java
// Implementing Trie Insertion

public class Trie {
    private TrieNode root;

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

    public void insert(String word) {
        TrieNode current = root;

        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);

            if (!current.containsKey(ch)) {
                current.put(ch, new TrieNode());
            }

            current = current.get(ch);
        }

        current.setEnd();
    }
}
```

Which of the following steps are involved in inserting a new word into a trie?

A) Traverse the trie until the end of the word B) Start from the root node and initialize a pointer C) Create a new node for each character D) Mark the last node as the end of the word

Select the correct options:

In a trie, deletion refers to removing a word from the trie.

The deletion operation can be done by following these steps:

1. Start from the root node and initialize a pointer current to track the current node.
2. Iterate through each character in the word.
3. Check if the current node contains a link for the character. If not, return false as the word is not present in the trie.
4. Update the current pointer to the next node.
5. Repeat steps 3-4 for all characters in the word.
6. After iterating through all characters, check if the current node is the end of a word. If not, return false as the word is not present in the trie.
7. Mark the current node as not the end of a word.
8. Check if the current node has any children. If not, remove the link to the current node from its parent.
9. Repeat steps 7-8 for all characters in the word, from the last character to the first.

Here is an example implementation of the delete method in the Trie class:

public void delete(String word) {
    delete(root, word, 0);
}

private boolean delete(TrieNode current, String word, int index) {
    if (index == word.length()) {
        if (!current.isEndOfWord()) {
            return false;
        }
        current.setEndOfWord(false);
        return current.getChildren().isEmpty();
    }

    char ch = word.charAt(index);
    TrieNode node = current.getChildren().get(ch);
    if (node == null) {
        return false;
    }

    boolean shouldDeleteCurrentNode = delete(node, word, index + 1);
    if (shouldDeleteCurrentNode) {
        current.getChildren().remove(ch);
        return current.getChildren().isEmpty();
    }

    return false;
}

```java
class TrieNode {
    private Map<Character, TrieNode> children;
    private boolean isEndOfWord;

    public TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }

    public Map<Character, TrieNode> getChildren() {
        return children;
    }

    public boolean isEndOfWord() {
        return isEndOfWord;
    }

    public void setEndOfWord(boolean endOfWord) {
        isEndOfWord = endOfWord;
    }
}

class Trie {
    private TrieNode root;

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

    public void insert(String word) {
        TrieNode current = root;

        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);

            if (!current.getChildren().containsKey(ch)) {
                current.getChildren().put(ch, new TrieNode());
            }

            current = current.getChildren().get(ch);
        }

        current.setEndOfWord(true);
    }

    public void delete(String word) {
        delete(root, word, 0);
    }

    private boolean delete(TrieNode current, String word, int index) {
        if (index == word.length()) {
            if (!current.isEndOfWord()) {
                return false;
            }
            current.setEndOfWord(false);
            return current.getChildren().isEmpty();
        }

        char ch = word.charAt(index);
        TrieNode node = current.getChildren().get(ch);
        if (node == null) {
            return false;
        }

        boolean shouldDeleteCurrentNode = delete(node, word, index + 1);
        if (shouldDeleteCurrentNode) {
            current.getChildren().remove(ch);
            return current.getChildren().isEmpty();
        }

        return false;
    }
}

```

In a trie, deletion refers to removing a word from the trie.

To search for a word in a trie, follow these steps:

1. Start from the root node and initialize a pointer current to track the current node.
2. Iterate through each character in the word.
3. Check if the current node contains a link for the character. If not, the word is not present in the trie.
4. Update the current pointer to the next node.
5. Repeat steps 3-4 for all characters in the word.
6. After iterating through all characters, check if the current node marks the end of a word. If yes, the word is present in the trie. Otherwise, the word is not present.

Here is an example implementation of the search method in the Trie class:

```java
class Trie {

    // ... other methods

    public boolean search(String word) {
        TrieNode current = root;

        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            TrieNode node = current.getChildren().get(ch);

            // If the current node doesn't contain a link for the character,
            // the word is not present in the trie
            if (node == null) {
                return false;
            }

            current = node;
        }

        // After iterating through all characters,
        // the word is present if the current node marks the end of a word
        return current.isEndOfWord();
    }

    // ... other methods

}
```

What is the time complexity of searching for a word in a trie with n nodes?

A practical use case of tries is autocomplete functionality. Tries provide an efficient way to implement autocomplete or suggestion features in text editors or search engines.

In an autocomplete system, given a prefix entered by the user, the system needs to suggest a list of words that match that prefix. For example, if the user types "app", the system should suggest words like "apple" and "application".

Tries are well-suited for this task because they can efficiently find all words that match a given prefix. Starting from the root node, we can navigate through the trie following the characters in the prefix. If we reach a node where the characters don't match, we can immediately stop the traversal and return an empty list of suggestions. If we reach the end of the prefix, we can use a depth-first search to find all words below that node, which provides us with the autocomplete suggestions.

Here's an example implementation of an autocomplete class using a trie in Java:

import java.util.ArrayList;
import java.util.List;

public class Autocomplete {

    private TrieNode root;

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

    // Insert a word into the trie
    public void insert(String word) {
        TrieNode current = root;

        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }

        current.isWord = true;
    }

    // Get autocomplete suggestions for a given prefix
    public List<String> autocomplete(String prefix) {
        TrieNode current = root;
        List<String> suggestions = new ArrayList<>();

        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                return suggestions;
            }
            current = current.children[index];
        }

        autocompleteHelper(prefix, current, suggestions);

        return suggestions;
    }

    private void autocompleteHelper(String prefix, TrieNode node, List<String> suggestions) {
        if (node.isWord) {
            suggestions.add(prefix);
        }

        for (char c = 'a'; c <= 'z'; c++) {
            int index = c - 'a';
            if (node.children[index] != null) {
                autocompleteHelper(prefix + c, node.children[index], suggestions);
            }
        }
    }

    private class TrieNode {
        TrieNode[] children;
        boolean isWord;

        public TrieNode() {
            this.children = new TrieNode[26];
            this.isWord = false;
        }
    }

    public static void main(String[] args) {
        Autocomplete autocomplete = new Autocomplete();
        autocomplete.insert("apple");
        autocomplete.insert("application");
        autocomplete.insert("banana");

        List<String> suggestions = autocomplete.autocomplete("app");
        System.out.println(suggestions); // Output: [apple, application]
    }
}

```java
```java
import java.util.ArrayList;
import java.util.List;

public class Autocomplete {

    private TrieNode root;

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

    // Insert a word into the trie
    public void insert(String word) {
        TrieNode current = root;

        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }

        current.isWord = true;
    }

    // Get autocomplete suggestions for a given prefix
    public List<String> autocomplete(String prefix) {
        TrieNode current = root;
        List<String> suggestions = new ArrayList<>();

        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                return suggestions;
            }
            current = current.children[index];
        }

        autocompleteHelper(prefix, current, suggestions);

        return suggestions;
    }

    private void autocompleteHelper(String prefix, TrieNode node, List<String> suggestions) {
        if (node.isWord) {
            suggestions.add(prefix);
        }

        for (char c = 'a'; c <= 'z'; c++) {
            int index = c - 'a';
            if (node.children[index] != null) {
                autocompleteHelper(prefix + c, node.children[index], suggestions);
            }
        }
    }

    private class TrieNode {
        TrieNode[] children;
        boolean isWord;

        public TrieNode() {
            this.children = new TrieNode[26];
            this.isWord = false;
        }
    }

    public static void main(String[] args) {
        Autocomplete autocomplete = new Autocomplete();
        autocomplete.insert("apple");
        autocomplete.insert("application");
        autocomplete.insert("banana");

        List<String> suggestions = autocomplete.autocomplete("app");
        System.out.println(suggestions); // Output: [apple, application]
    }
}
```

Tries are efficient data structures for implementing autocomplete functionality in text editors or search engines.

Generating complete for this lesson!