A trie (pronounced "try") is like a word search puzzle, where each path from the start creates a different word letter by letter. Also known as a prefix tree, tries are special trees that store strings by breaking them down into individual characters. Unlike regular trees that store complete values at each node, tries build words character by character along paths, making them perfect for tasks like autocomplete or spell checking.

Tries allow us to add words by creating paths of letters, and find words by following these paths one letter at a time. Since words with the same beginning share the same path, tries make it quick and easy to look up words or check if they exist.

The efficiency of tries depends on the alphabet size (often shown as Σ), which is simply how many different characters we might use. For example, if we're only storing lowercase English words, our alphabet size is 26. This matters because each node in our trie needs to be ready to handle any character that might come next in a word.

A trie node is like a single letter in a word puzzle, where each node represents one character. Instead of storing complete words, each node uses a hashmap to track which letters can come next. This means words that start with the same letters can share the same path - for example, car and cat would share the nodes for c and a before splitting into different paths.

# Definition of a trie node
class TrieNode:
    def __init__(self):
        self.children = {}
        self.isWord = False

Each node also needs to know if it marks the end of a word, which we track using a boolean flag that indicates whether this node completes a valid word. For example, in a trie containing both do and done, the node for o needs to indicate it completes a word, while also having a child node for n. Tries makes it efficient to check if a string is a complete word or just part of a longer word.

Inserting into a trie is like creating a new path through a forest, where we add new routes only when we need them. Starting at the root node, we move through each character of our word, either following existing paths or creating new ones. If we want to insert cow and already have cook, we can reuse the path for co and only create a new node for w, making tries memory efficient.

# Definition of a trie node
class TrieNode:
    def __init__(self):
        self.children = {}
        self.isWord = False


class Trie:
    def __init__(self):
        # Create a root node for the trie
        self.root = TrieNode()
        
    def insert(self, word: str) -> None:
        # Start at the root of the trie
        cur = self.root
        for char in word:
            # If the current character is not in the trie, add it
            if char not in cur.children:
                cur.children[char] = TrieNode()
            # Shift the cur pointer
            cur = cur.children[char]
        # Mark the last node as the end of the word (cur is on last node)
        cur.isWord = True

After creating the path for our word, we need to mark its end. By setting an end-of-word flag on the final node, we can distinguish between complete words and prefixes. This isWord boolean flag helps us avoid treating partial matches as valid words when searching, and lets us store multiple words that share the same beginning while still knowing exactly where each word ends.

Deleting from a trie requires more care than insertion because we need to preserve shared paths used by other words. The first step is simple - we follow the path of characters and unmark the end-of-word flag when we find our target word. For example, if we have both to and top stored and want to delete to, we just remove its word marker while keeping all nodes intact since they're still needed for top.

# Definition of a trie node
class TrieNode:
    def __init__(self):
        self.children = {}
        self.isWord = False


class Trie:
    def __init__(self):
        # Create a root node for the trie
        self.root = TrieNode()

    def delete(self, word: str) -> None:
        # Start at the root of the trie
        cur = self.root
        for char in word:
            # If the current character is not in the trie, just return
            if char not in cur.children:
                return  # Word not found
            # Shift the cur pointer
            cur = cur.children[char]
            
        # If the word isn't found, just return
        if not cur.isWord:
            return
        # Unmark as end of word
        cur.isWord = False

The deletion process follows the word's path through the trie, checking each character one by one. If at any point we can't find the next character, or if we reach the end and find it's not marked as a word, we simply return since there's nothing to delete. When we do find the word, we just set its end-of-word flag to False, keeping the nodes in place for any other words that might share this path.

Searching in a trie is like following a path of breadcrumbs, where we check each character one at a time starting from the root. We follow child nodes that match each character in our word, and if we ever can't find a matching child, we know the word isn't in our trie. Even if we make it to the end of our word, we still need to check if that final node is marked as a word - this helps us distinguish between complete words and just parts of longer words.

# Definition of a trie node
class TrieNode:
    def __init__(self):
        self.children = {}
        self.isWord = False


class Trie:
    def __init__(self):
        # Create a root node for the trie
        self.root = TrieNode()

    def search(self, word: str) -> bool:
        # Start at the root of the trie
        cur = self.root
        for char in word:
            # If the current character isn't in the trie, return False
            if char not in cur.children:
                return False
            # Shift the cur pointer
            cur = cur.children[char]
        # Check if the last node is the end of the word
        return cur.isWord

Searching for prefixes works almost the same way, but with one key difference: we don't need to check the word flag at the end. If we can follow the path of characters in our prefix to reach a valid node, then we've found our prefix - it doesn't matter if that node marks the end of a word or not. This makes tries especially efficient for tasks like autocomplete where we need to find all words that start with a given prefix.

Tries efficiently store and search words or sequences of strings. They are useful for tasks involving prefixes, such as autocomplete systems or spell checkers. To get the most out of tries in coding interviews, here are some essential tips and tricks: