prefix tree → a tree-based data structure where each node represents a single character of a string

1. Define the Node Blueprint

Each individual node in a Trie needs two main components:

• children: A container (usually a hash map/dictionary or a fixed array of size 26 for English letters) to link characters to their respective child nodes.
• is_end_of_word: A boolean flag that marks whether a complete word finishes at that exact node.

class TrieNode:
    def __init__(self):
        # Maps a character string (e.g., 'a') to a TrieNode instance
        self.children = {}
        # True if the node marks the completion of a valid word
        self.is_end_of_word = False

2. Define the Trie Container

The main Trie class holds a single empty TrieNode acting as the structural entry point (the root).

class Trie:
    def __init__(self):
        # The entry point of the tree represents an empty prefix
        self.root = TrieNode()

3. Implement Core Methods

insert()

To add a word, start at the root node and look at each letter sequentially. If the letter does not exist as a key in the current node's dictionary, create a new for it. Move your tracking pointer to that child node and repeat. Flip the flag to at the very last letter node.

		def insert(self, word: str) -> None:
		        current = self.root
		        for char in word:
		            # If the character path doesn't exist, build it
		            if char not in current.children:
		                current.children[char] = TrieNode()
		            # Move deeper into the tree structure
		            current = current.children[char]
		        # Mark the final node as a complete word
		        current.is_end_of_word = True

search()

Start at the root and follow the letters of your search query. If a character is missing from the dictionary at any level, the word is not in the tree—return immediately. If you successfully map every character, return the node's boolean status.

		def search(self, word: str) -> bool:
		        current = self.root
		        for char in word:
		            if char not in current.children:
		                return False
		            current = current.children[char]
		        # Return True only if it is a complete stored word
		        return current.is_end_of_word

prefix search()

This operates exactly like the standard search method, but it bypasses the final boolean flag check. If the character sequence exists entirely in the tree, return (even if no complete word ends there).

    def starts_with(self, prefix: str) -> bool:
        current = self.root
        for char in prefix:
            if char not in current.children:
                return False
            current = current.children[char]
        # The prefix pathway exists fully
        return True

Complexity Analysis