Data Structures & Algorithms

       root
      / | \
     a  b  c
    /   |   \
   p    a    a
   |    |    |
   p    t    t  ← "bat", "cat" end here
   |
   l    
   |
   e  ← "apple" ends here

class TrieNode:
    def __init__(self):
        self.children = {}  # char → TrieNode
        self.is_end = False  # Marks end of a word

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        """Add a word to the Trie — O(m)"""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    
    def search(self, word):
        """Check if EXACT word exists — O(m)"""
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end  # Must be end of a word!
    
    def starts_with(self, prefix):
        """Check if any word starts with prefix — O(m)"""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True  # Prefix found!

# Usage
trie = Trie()
trie.insert("apple")
trie.insert("app")
trie.insert("bat")

print(trie.search("app"))       # True
print(trie.search("ap"))        # False (not a complete word)
print(trie.starts_with("ap"))   # True (prefix exists)

Initially: {0} {1} {2} {3} {4}  (each element is its own group)

Union(0, 1): {0, 1} {2} {3} {4}
Union(2, 3): {0, 1} {2, 3} {4}
Union(1, 3): {0, 1, 2, 3} {4}

Find(0) == Find(3)?  → Yes! (same group)
Find(0) == Find(4)?  → No!  (different groups)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # Each element is its own parent
        self.rank = [0] * n           # For union by rank
    
    def find(self, x):
        """Find root of x's group — with Path Compression"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Flatten tree!
        return self.parent[x]
    
    def union(self, x, y):
        """Merge groups of x and y — with Union by Rank"""
        px, py = self.find(x), self.find(y)
        
        if px == py:
            return False  # Already in same group
        
        # Attach smaller tree under larger tree
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
        elif self.rank[px] > self.rank[py]:
            self.parent[py] = px
        else:
            self.parent[py] = px
            self.rank[px] += 1
        
        return True
    
    def connected(self, x, y):
        """Check if x and y are in the same group"""
        return self.find(x) == self.find(y)

# Usage
uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
uf.union(1, 3)

print(uf.connected(0, 3))  # True (same group)
print(uf.connected(0, 4))  # False (different groups)

# Trie — Insert and Search
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

# Union-Find — Core Pattern
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])  # Path compression
    return parent[x]