Trie Data Structure: Complete Guide

class TrieNode:
    """A single node in the Trie"""
    
    def __init__(self):
        self.children = {}           # Map: character -> TrieNode
        self.is_end  # Marks_of_word = False complete word
        self.frequency = 0           # For autocomplete ranking
        self.metadata = {}           # Additional data (definitions, etc.)
    
    def __repr__(self):
        return f"TrieNode(children={list(self.children.keys())}, word_end={self.is_end_of_word})"

class Trie:
    """Complete Trie implementation with insert, search, and prefix operations"""
    
    def __init__(self):
        self.root = TrieNode()
        self.word_count = 0
    
    def insert(self, word: str) -> None:
        """Insert a word into the Trie"""
        node = self.root
        
        for char in word.lower():
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        
        if not node.is_end_of_word:
            node.is_end_of_word = True
            self.word_count += 1
    
    def search(self, word: str) -> bool:
        """Check if exact word exists in Trie"""
        node = self._find_node(word.lower())
        return node is not None and node.is_end_of_word
    
    def starts_with(self, prefix: str) -> bool:
        """Check if any word starts with given prefix"""
        return self._find_node(prefix.lower()) is not None
    
    def _find_node(self, prefix: str) -> TrieNode | None:
        """Find node corresponding to prefix"""
        node = self.root
        
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        
        return node
    
    def autocomplete(self, prefix: str, limit: int = 10) -> list[str]:
        """Return words starting with prefix, ranked by frequency"""
        node = self._find_node(prefix.lower())
        
        if node is None:
            return []
        
        results = []
        self._collect_words(node, prefix, results)
        
        # Sort by frequency (most frequent first)
        results.sort(key=lambda x: x[1], reverse=True)
        
        return [word for word, freq in results[:limit]]
    
    def _collect_words(self, node: TrieNode, current_prefix: str, results: list) -> None:
        """Recursively collect all words from a node"""
        if node.is_end_of_word:
            results.append((current_prefix, node.frequency))
        
        for char, child_node in node.children.items():
            self._collect_words(child_node, current_prefix + char, results)
    
    def delete(self, word: str) -> bool:
        """Delete word from Trie"""
        def _delete_recursive(node: TrieNode, word: str, depth: int) -> bool:
            if depth == len(word):
                if not node.is_end_of_word:
                    return False
                node.is_end_of_word = False
                return len(node.children) == 0
            
            char = word[depth]
            if char not in node.children:
                return False
            
            should_delete_child = _delete_recursive(
                node.children[char], word, depth + 1
            )
            
            if should_delete_child:
                del node.children[char]
                return len(node.children) == 0 and not node.is_end_of_word
            
            return False
        
        word_lower = word.lower()
        if self.search(word):
            _delete_recursive(self.root, word_lower, 0)
            self.word_count -= 1
            return True
        return False
    
    def starts_with_prefix(self, prefix: str) -> list[str]:
        """Return all words starting with prefix"""
        node = self._find_node(prefix.lower())
        
        if node is None:
            return []
        
        results = []
        self._collect_words(node, prefix.lower(), results)
        return [word for word, _ in results]

import java.util.*;

public class Trie {
    private final TrieNode root;
    private int wordCount;
    
    private static class TrieNode {
        Map<Character, TrieNode> children;
        boolean isEndOfWord;
        int frequency;
        
        TrieNode() {
            children = new HashMap<>();
            isEndOfWord = false;
            frequency = 0;
        }
    }
    
    public Trie() {
        root = new TrieNode();
        wordCount = 0;
    }
    
    public void insert(String word) {
        TrieNode current = root;
        
        for (char c : word.toLowerCase().toCharArray()) {
            current.children.putIfAbsent(c, new TrieNode());
            current = current.children.get(c);
        }
        
        if (!current.isEndOfWord) {
            current.isEndOfWord = true;
            wordCount++;
        }
    }
    
    public boolean search(String word) {
        TrieNode node = findNode(word.toLowerCase());
        return node != null && node.isEndOfWord;
    }
    
    public boolean startsWith(String prefix) {
        return findNode(prefix.toLowerCase()) != null;
    }
    
    private TrieNode findNode(String prefix) {
        TrieNode current = root;
        
        for (char c : prefix.toCharArray()) {
            if (!current.children.containsKey(c)) {
                return null;
            }
            current = current.children.get(c);
        }
        
        return current;
    }
    
    public List<String> autocomplete(String prefix, int limit) {
        TrieNode node = findNode(prefix.toLowerCase());
        List<String> results = new ArrayList<>();
        
        if (node != null) {
            collectWords(node, prefix.toLowerCase(), results);
            results.sort((a, b) -> b.compareTo(a)); // Sort by length/frequency
        }
        
        return results.subList(0, Math.min(limit, results.size()));
    }
    
    private void collectWords(TrieNode node, String prefix, List<String> results) {
        if (node.isEndOfWord) {
            results.add(prefix);
        }
        
        for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
            collectWords(entry.getValue(), prefix + entry.getKey(), results);
        }
    }
}

class AutocompleteSystem:
    """Production-ready autocomplete using Trie"""
    
    def __init__(self, max_suggestions: int = 5):
        self.trie = Trie()
        self.max_suggestions = max_suggestions
        self.user_sessions = {}  # Track user-specific preferences
    
    def load_dictionary(self, words: list[tuple[str, int]]) -> None:
        """Load dictionary with frequency weights"""
        for word, frequency in words:
            self.trie.insert(word)
            # Store frequency in last node
            node = self.trie._find_node(word.lower())
            if node:
                node.frequency = frequency
    
    def get_suggestions(self, query: str, user_id: str = None) -> list[dict]:
        """Get autocomplete suggestions for query"""
        if not query:
            return []
        
        prefix = query.lower().strip()
        
        # Get base suggestions from trie
        suggestions = self.trie.autocomplete(prefix, limit=10)
        
        # Apply user personalization
        if user_id and user_id in self.user_sessions:
            suggestions = self._personalize(suggestions, user_id)
        
        # Calculate relevance scores
        scored = []
        for word in suggestions[:self.max_suggestions]:
            node = self.trie._find_node(word.lower())
            base_score = node.frequency if node else 0
            
            # Boost exact prefix matches
            if word.lower().startswith(prefix):
                base_score *= 1.5
            
            # Boost recent selections from this session
            if user_id and word in self.user_sessions.get(user_id, set()):
                base_score *= 2.0
            
            scored.append({
                'word': word,
                'score': base_score,
                'type': 'history' if user_id and word in self.user_sessions.get(user_id, set()) else 'suggestion'
            })
        
        return sorted(scored, key=lambda x: x['score'], reverse=True)[:self.max_suggestions]
    
    def record_selection(self, word: str, user_id: str) -> None:
        """Record user selection for personalization"""
        if user_id not in self.user_sessions:
            self.user_sessions[user_id] = set()
        self.user_sessions[user_id].add(word.lower())
        
        # Update frequency in trie
        node = self.trie._find_node(word.lower())
        if node:
            node.frequency += 1


# Example usage
autocomplete = AutocompleteSystem(max_suggestions=5)

# Load common words with frequencies
dictionary = [
    ("python", 1000),
    ("python programming", 500),
    ("python tutorial", 300),
    ("python for beginners", 200),
    ("javascript", 900),
    ("java tutorial", 400),
    ("java programming", 350),
]
autocomplete.load_dictionary(dictionary)

# Get suggestions
suggestions = autocomplete.get_suggestions("pyt")
print(suggestions)
# Output: [{'word': 'python', 'score': 1500.0, 'type': 'suggestion'}, ...]

class IPRoutingTable:
    """Longest Prefix Match using Trie"""
    
    class RoutingNode:
        def __init__(self):
            self.children = {}
            self.is_route = False
            self.next_hop = None
    
    def __init__(self):
        self.root = self.RoutingNode()
    
    def add_route(self, cidr: str, next_hop: str) -> None:
        """Add routing entry"""
        ip, prefix_len = cidr.split('/')
        binary_ip = self._ip_to_binary(ip)
        
        node = self.root
        for i in range(int(prefix_len)):
            bit = binary_ip[i]
            if bit not in node.children:
                node.children[bit] = self.RoutingNode()
            node = node.children[bit]
        
        node.is_route = True
        node.next_hop = next_hop
    
    def lookup(self, ip: str) -> str:
        """Find longest matching prefix"""
        binary_ip = self._ip_to_binary(ip)
        node = self.root
        longest_match = None
        
        for bit in binary_ip:
            if bit in node.children:
                node = node.children[bit]
                if node.is_route:
                    longest_match = node.next_hop
            else:
                break
        
        return longest_match or "default"
    
    @staticmethod
    def _ip_to_binary(ip: str) -> str:
        """Convert IP to binary string"""
        return ''.join(f'{int(octet):08b}' for octet in ip.split('.'))

class WordGameSolver:
    """Solve word games using Trie"""
    
    def __init__(self, dictionary: list[str]):
        self.trie = Trie()
        for word in dictionary:
            self.trie.insert(word)
    
    def find_words(self, letters: str, min_length: int = 3) -> list[str]:
        """Find all valid words from letters (Boggle-style)"""
        valid_words = []
        visited = set()
        
        def dfs(position: int, current_prefix: str):
            if len(current_prefix) >= min_length:
                if self.trie.search(current_prefix):
                    valid_words.append(current_prefix)
            
            if not self.trie.starts_with(current_prefix):
                return
            
            for i in range(len(letters)):
                if i not in visited:
                    visited.add(i)
                    dfs(i, current_prefix + letters[i])
                    visited.remove(i)
        
        dfs(0, "")
        return valid_words

class CompressedTrie:
    """Space-optimized Trie using path compression"""
    
    def __init__(self):
        self.root = {'children': {}, 'end': False}
    
    def insert(self, word: str) -> None:
        """Insert with automatic compression"""
        self._insert_recursive(self.root, word, 0)
    
    def _insert_recursive(self, node: dict, word: str, depth: int) -> None:
        """Recursive insertion with path compression"""
        if depth == len(word):
            node['end'] = True
            return
        
        char = word[depth]
        
        # Find or create child
        if char not in node['children']:
            # Check for potential compression
            next_char = word[depth + 1] if depth + 1 < len(word) else None
            
            # Create compressed node if beneficial
            remaining = word[depth:]
            if self._should_compress(remaining):
                node['children'][remaining] = {'end': True, 'children': {}}
                return
        
        if word[depth:] in node['children']:
            node['children'][word[depth:]]['end'] = True
        else:
            self._insert_recursive(node['children'], word, depth + 1)
    
    def _should_compress(self, remaining: str) -> bool:
        """Determine if compression is worthwhile"""
        return len(remaining) > 3