from dataclasses import dataclass, field
from typing import Optional, Generic, TypeVar
from collections import defaultdict, deque, OrderedDict, Counter
from heapq import heappush, heappop, heapify
T = TypeVar('T')
@dataclass
class TreeNode:
value: T
left: Optional["TreeNode[T]"] = None
right: Optional["TreeNode[T]"] = None
def inorder_traversal(root: Optional[TreeNode[T]]) -> list[T]:
result: list[T] = []
if root:
result.extend(inorder_traversal(root.left))
result.append(root.value)
result.extend(inorder_traversal(root.right))
return result
def preorder_traversal(root: Optional[TreeNode[T]]) -> list[T]:
result: list[T] = []
if root:
result.append(root.value)
result.extend(preorder_traversal(root.left))
result.extend(preorder_traversal(root.right))
return result
def postorder_traversal(root: Optional[TreeNode[T]]) -> list[T]:
result: list[T] = []
if root:
result.extend(postorder_traversal(root.left))
result.extend(postorder_traversal(root.right))
result.append(root.value)
return result
def level_order_traversal(root: Optional[TreeNode[T]]) -> list[list[T]]:
if not root:
return []
result: list[list[T]] = []
queue: deque[TreeNode[T]] = deque([root])
while queue:
level: list[T] = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
@dataclass
class Graph:
adjacency: dict[str, list[str]] = field(default_factory=dict)
def add_edge(self, u: str, v: str, bidirectional: bool = True) -> None:
if u not in self.adjacency:
self.adjacency[u] = []
self.adjacency[u].append(v)
if bidirectional:
if v not in self.adjacency:
self.adjacency[v] = []
self.adjacency[v].append(u)
def dfs(self, start: str) -> list[str]:
visited: set[str] = set()
result: list[str] = []
def visit(node: str) -> None:
if node in visited:
return
visited.add(node)
result.append(node)
for neighbor in self.adjacency.get(node, []):
visit(neighbor)
visit(start)
return result
def bfs(self, start: str) -> list[str]:
visited: set[str] = {start}
result: list[str] = [start]
queue: deque[str] = deque([start])
while queue:
node = queue.popleft()
for neighbor in self.adjacency.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
result.append(neighbor)
queue.append(neighbor)
return result
class PriorityQueue(Generic[T]):
def __init__(self) -> None:
self._heap: list[tuple[int, int, T]] = []
self._counter = 0
def push(self, item: T, priority: int) -> None:
heappush(self._heap, (priority, self._counter, item))
self._counter += 1
def pop(self) -> T:
if not self._heap:
raise IndexError("Priority queue is empty")
return heappop(self._heap)[2]
def __len__(self) -> int:
return len(self._heap)
class DisjointSet:
def __init__(self, items: list[str]) -> None:
self.parent: dict[str, str] = {item: item for item in items}
self.rank: dict[str, int] = {item: 0 for item in items}
def find(self, x: str) -> str:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x: str, y: str) -> None:
px, py = self.find(x), self.find(y)
if px == py:
return
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
def trie_example():
Trie = lambda: defaultdict(Trie)
trie: defaultdict = Trie()
words = ["apple", "app", "application", "apply"]
for word in words:
node = trie
for char in word:
node = node[char]
node["$"] = word
return trie
count = Counter(["a", "b", "a", "c", "b", "a"])
ordered = OrderedDict([("a", 1), ("b", 2), ("c", 3)])