| 1 | 1 | class Zipper: |
| 2 | | # Tree is a dict with keys "value" (int), "left" (dict or None), "right" (dict or None) |
| 2 | """ |
| 3 | A zipper for navigating and manipulating a binary tree. |
| 4 | |
| 5 | The zipper maintains a focus on a specific node in the tree, allowing |
| 6 | movement through the tree structure and modifications while preserving |
| 7 | immutability by returning new zipper instances. |
| 8 | """ |
| 9 | |
| 10 | def __init__(self, tree, breadcrumbs=None): |
| 11 | """ |
| 12 | Initialize a Zipper instance. |
| 13 | |
| 14 | Args: |
| 15 | tree (dict): The current subtree that is focused |
| 16 | breadcrumbs (list): A list of breadcrumb dictionaries tracking the path to the focus |
| 17 | """ |
| 18 | self.tree = tree |
| 19 | self.breadcrumbs = breadcrumbs or [] |
| 20 | |
| 3 | 21 | @staticmethod |
| 4 | 22 | def from_tree(tree: dict) -> "Zipper": |
| 5 | | pass |
| 23 | """ |
| 24 | Create a zipper from a binary tree. |
| 25 | |
| 26 | Args: |
| 27 | tree (dict): A binary tree with keys "value", "left", and "right" |
| 28 | |
| 6 | 29 | |
| 30 | Returns: |
| 31 | Zipper: A new zipper focused on the root of the tree |
| 32 | """ |
| 33 | # Edge Case: Handle None tree input |
| 34 | if tree is None: |
| 35 | return None |
| 36 | return Zipper(tree) |
| 37 | |
| 7 | 38 | def value(self) -> int: |
| 8 | | pass |
| 39 | """ |
| 40 | Get the value of the focus node. |
| 41 | |
| 9 | 42 | |
| 43 | Returns: |
| 44 | int: The value of the current node |
| 45 | """ |
| 46 | # Edge Case: Handle None tree |
| 47 | if self.tree is None: |
| 48 | return None |
| 49 | return self.tree["value"] |
| 50 | |
| 10 | 51 | def set_value(self, value: int) -> "Zipper": |
| 11 | | pass |
| 52 | """ |
| 53 | Set the value of the focus node, returning a new zipper. |
| 54 | |
| 55 | Args: |
| 56 | value (int): The new value for the focus node |
| 57 | |
| 12 | 58 | |
| 59 | Returns: |
| 60 | Zipper: A new zipper with the updated value |
| 61 | """ |
| 62 | # Edge Case: Handle None tree |
| 63 | if self.tree is None: |
| 64 | return self |
| 65 | new_tree = { |
| 66 | "value": value, |
| 67 | "left": self.tree["left"], |
| 68 | "right": self.tree["right"] |
| 69 | } |
| 70 | return Zipper(new_tree, self.breadcrumbs) |
| 71 | |
| 13 | 72 | def left(self) -> "Zipper | None": |
| 14 | | pass |
| 73 | """ |
| 74 | Move the focus to the left child, returning a new zipper. |
| 75 | |
| 15 | 76 | |
| 77 | Returns: |
| 78 | Zipper | None: A new zipper focused on the left child, or None if no left child |
| 79 | """ |
| 80 | # Edge Case: Handle None tree |
| 81 | if self.tree is None or self.tree["left"] is None: |
| 82 | return None |
| 83 | |
| 84 | # Create a breadcrumb to remember the path |
| 85 | breadcrumb = { |
| 86 | "parent": { |
| 87 | "value": self.tree["value"], |
| 88 | "right": self.tree["right"] |
| 89 | }, |
| 90 | "is_left": True |
| 91 | } |
| 92 | |
| 93 | return Zipper(self.tree["left"], self.breadcrumbs + [breadcrumb]) |
| 94 | |
| 16 | 95 | def set_left(self, tree: dict | None) -> "Zipper": |
| 17 | | pass |
| 96 | """ |
| 97 | Set the left child of the focus node, returning a new zipper. |
| 98 | |
| 99 | Args: |
| 100 | tree (dict | None): The new left subtree |
| 101 | |
| 18 | 102 | |
| 103 | Returns: |
| 104 | Zipper: A new zipper with the updated left child |
| 105 | """ |
| 106 | # Edge Case: Handle None tree |
| 107 | if self.tree is None: |
| 108 | return self |
| 109 | new_tree = { |
| 110 | "value": self.tree["value"], |
| 111 | "left": tree, |
| 112 | "right": self.tree["right"] |
| 113 | } |
| 114 | return Zipper(new_tree, self.breadcrumbs) |
| 115 | |
| 19 | 116 | def right(self) -> "Zipper | None": |
| 20 | | pass |
| 117 | """ |
| 118 | Move the focus to the right child, returning a new zipper. |
| 119 | |
| 21 | 120 | |
| 121 | Returns: |
| 122 | Zipper | None: A new zipper focused on the right child, or None if no right child |
| 123 | """ |
| 124 | # Edge Case: Handle None tree |
| 125 | if self.tree is None or self.tree["right"] is None: |
| 126 | return None |
| 127 | |
| 128 | # Create a breadcrumb to remember the path |
| 129 | breadcrumb = { |
| 130 | "parent": { |
| 131 | "value": self.tree["value"], |
| 132 | "left": self.tree["left"] |
| 133 | }, |
| 134 | "is_left": False |
| 135 | } |
| 136 | |
| 137 | return Zipper(self.tree["right"], self.breadcrumbs + [breadcrumb]) |
| 138 | |
| 22 | 139 | def set_right(self, tree: dict | None) -> "Zipper": |
| 23 | | pass |
| 140 | """ |
| 141 | Set the right child of the focus node, returning a new zipper. |
| 142 | |
| 143 | Args: |
| 144 | tree (dict | None): The new right subtree |
| 145 | |
| 24 | 146 | |
| 147 | Returns: |
| 148 | Zipper: A new zipper with the updated right child |
| 149 | """ |
| 150 | # Edge Case: Handle None tree |
| 151 | if self.tree is None: |
| 152 | return self |
| 153 | new_tree = { |
| 154 | "value": self.tree["value"], |
| 155 | "left": self.tree["left"], |
| 156 | "right": tree |
| 157 | } |
| 158 | return Zipper(new_tree, self.breadcrumbs) |
| 159 | |
| 25 | 160 | def up(self) -> "Zipper | None": |
| 26 | | pass |
| 161 | """ |
| 162 | Move the focus to the parent node, returning a new zipper. |
| 163 | |
| 27 | 164 | |
| 165 | Returns: |
| 166 | Zipper | None: A new zipper focused on the parent, or None if at root |
| 167 | """ |
| 168 | # Edge Case: Handle when already at root (no breadcrumbs) |
| 169 | if not self.breadcrumbs: |
| 170 | return None |
| 171 | |
| 172 | # Get the last breadcrumb |
| 173 | last_breadcrumb = self.breadcrumbs[-1] |
| 174 | parent = last_breadcrumb["parent"] |
| 175 | is_left = last_breadcrumb["is_left"] |
| 176 | |
| 177 | # Reconstruct the parent tree with the current subtree in the correct position |
| 178 | new_tree = { |
| 179 | "value": parent["value"], |
| 180 | "left": self.tree if is_left else parent.get("left"), |
| 181 | "right": parent.get("right") if is_left else self.tree |
| 182 | } |
| 183 | |
| 184 | return Zipper(new_tree, self.breadcrumbs[:-1]) |
| 185 | |
| 28 | 186 | def to_tree(self) -> dict: |
| 29 | | pass |
| 187 | """ |
| 188 | Get the entire binary tree from the zipper. |
| 189 | |
| 190 | |
| 191 | Returns: |
| 192 | dict: The complete binary tree |
| 193 | """ |
| 194 | # Start with the current tree |
| 195 | result = self.tree |
| 196 | |
| 197 | # Work backwards through breadcrumbs to reconstruct the full tree |
| 198 | for breadcrumb in reversed(self.breadcrumbs): |
| 199 | parent = breadcrumb["parent"] |
| 200 | is_left = breadcrumb["is_left"] |
| 201 | |
| 202 | if is_left: |
| 203 | result = { |
| 204 | "value": parent["value"], |
| 205 | "left": result, |
| 206 | "right": parent.get("right") |
| 207 | } |
| 208 | else: |
| 209 | result = { |
| 210 | "value": parent["value"], |
| 211 | "left": parent.get("left"), |
| 212 | "right": result |
| 213 | } |
| 214 | |
| 215 | return result |
| 216 | |
| 217 | def insert_before(self, tree: dict) -> "Zipper": |
| 218 | """ |
| 219 | Insert a new subtree before the focus node (as left sibling in binary tree), |
| 220 | it becomes the prev of the focus node, returning a new zipper. |
| 221 | |
| 222 | Args: |
| 223 | tree (dict): The new subtree to insert |
| 224 | |
| 225 | Returns: |
| 226 | Zipper: A new zipper with the inserted subtree |
| 227 | """ |
| 228 | # Edge Case: Handle when already at root (no breadcrumbs) |
| 229 | if not self.breadcrumbs: |
| 230 | # Can't insert before root, return self |
| 231 | return self |
| 232 | |
| 233 | # Get the last breadcrumb |
| 234 | last_breadcrumb = self.breadcrumbs[-1] |
| 235 | is_left = last_breadcrumb["is_left"] |
| 236 | |
| 237 | # If we're the right child, we can insert a left sibling |
| 238 | # If we're the left child, we can't insert before us in a binary tree |
| 239 | if not is_left: # We're the right child |
| 240 | # Reconstruct the entire tree with the insertion |
| 241 | full_tree = self.to_tree() |
| 242 | # Create a new zipper from the modified tree |
| 243 | new_zipper = Zipper.from_tree(full_tree) |
| 244 | # Navigate back to the same position |
| 245 | for breadcrumb in self.breadcrumbs[:-1]: |
| 246 | if breadcrumb["is_left"]: |
| 247 | new_zipper = new_zipper.left() |
| 248 | else: |
| 249 | new_zipper = new_zipper.right() |
| 250 | # Now we're at the parent level, navigate to the right child (our focus) |
| 251 | new_zipper = new_zipper.right() |
| 252 | return new_zipper |
| 253 | else: # We're the left child |
| 254 | # Can't insert before the left child in a binary tree |
| 255 | return self |
| 256 | |
| 257 | def prev(self) -> "Zipper | None": |
| 258 | """ |
| 259 | Move the focus to the previous sibling (left sibling in binary tree), returning a new zipper. |
| 260 | |
| 261 | Returns: |
| 262 | Zipper | None: A new zipper focused on the previous sibling, or None if no previous sibling |
| 263 | """ |
| 264 | # Edge Case: Handle when already at root (no breadcrumbs) |
| 265 | if not self.breadcrumbs: |
| 266 | return None |
| 267 | |
| 268 | # Get the last breadcrumb |
| 269 | last_breadcrumb = self.breadcrumbs[-1] |
| 270 | parent = last_breadcrumb["parent"] |
| 271 | is_left = last_breadcrumb["is_left"] |
| 272 | |
| 273 | # If we're the right child, move to the left child |
| 274 | if not is_left: |
| 275 | left_child = parent.get("left") |
| 276 | if left_child is not None: |
| 277 | # Create a new zipper focused on the left child |
| 278 | # We need to reconstruct the path to the left child |
| 279 | new_breadcrumbs = self.breadcrumbs[:-1] + [{ |
| 280 | "parent": { |
| 281 | "value": parent["value"], |
| 282 | "right": self.tree |
| 283 | }, |
| 284 | "is_left": True |
| 285 | }] |
| 286 | return Zipper(left_child, new_breadcrumbs) |
| 287 | |
| 288 | # If we're the left child, there's no previous sibling |
| 289 | return None |
| 290 | |
| 291 | def next(self) -> "Zipper | None": |
| 292 | """ |
| 293 | Move the focus to the next sibling (right sibling in binary tree), returning a new zipper. |
| 294 | |
| 295 | Returns: |
| 296 | Zipper | None: A new zipper focused on the next sibling, or None if no next sibling |
| 297 | """ |
| 298 | # Edge Case: Handle when already at root (no breadcrumbs) |
| 299 | if not self.breadcrumbs: |
| 300 | return None |
| 301 | |
| 302 | # Get the last breadcrumb |
| 303 | last_breadcrumb = self.breadcrumbs[-1] |
| 304 | parent = last_breadcrumb["parent"] |
| 305 | is_left = last_breadcrumb["is_left"] |
| 306 | |
| 307 | # If we're the left child, move to the right child |
| 308 | if is_left: |
| 309 | right_child = parent.get("right") |
| 310 | if right_child is not None: |
| 311 | # Create a new zipper focused on the right child |
| 312 | # We need to reconstruct the path to the right child |
| 313 | new_breadcrumbs = self.breadcrumbs[:-1] + [{ |
| 314 | "parent": { |
| 315 | "value": parent["value"], |
| 316 | "left": self.tree |
| 317 | }, |
| 318 | "is_left": False |
| 319 | }] |
| 320 | return Zipper(right_child, new_breadcrumbs) |
| 321 | |
| 322 | # If we're the right child, there's no next sibling |
| 323 | return None |
| 324 | |
| 325 | def insert_before(self, tree: dict) -> "Zipper": |
| 326 | """ |
| 327 | Insert a new subtree before the focus node (as left sibling in binary tree), |
| 328 | it becomes the prev of the focus node, returning a new zipper. |
| 329 | |
| 330 | Args: |
| 331 | tree (dict): The new subtree to insert |
| 332 | |
| 333 | Returns: |
| 334 | Zipper: A new zipper with the inserted subtree |
| 335 | """ |
| 336 | # Edge Case: Handle when already at root (no breadcrumbs) |
| 337 | if not self.breadcrumbs: |
| 338 | # Can't insert before root, return self |
| 339 | return self |
| 340 | |
| 341 | # Get the last breadcrumb |
| 342 | last_breadcrumb = self.breadcrumbs[-1] |
| 343 | parent = last_breadcrumb["parent"] |
| 344 | is_left = last_breadcrumb["is_left"] |
| 345 | |
| 346 | # If we're the right child, we can insert a left sibling |
| 347 | # If we're the left child, we can't insert before us in a binary tree |
| 348 | if not is_left: # We're the right child |
| 349 | # Create a new parent with the inserted tree as left child and self as right child |
| 350 | new_parent = { |
| 351 | "value": parent["value"], |
| 352 | "left": tree, |
| 353 | "right": self.tree |
| 354 | } |
| 355 | |
| 356 | # Update the breadcrumb trail to reflect that we're now the right child of the new parent |
| 357 | new_breadcrumbs = self.breadcrumbs[:-1] + [{ |
| 358 | "parent": { |
| 359 | "value": parent["value"], |
| 360 | "left": tree |
| 361 | }, |
| 362 | "is_left": False |
| 363 | }] |
| 364 | |
| 365 | # Return a new zipper focused on the same node but with updated parent structure |
| 366 | return Zipper(self.tree, new_breadcrumbs) |
| 367 | else: # We're the left child |
| 368 | # Can't insert before the left child in a binary tree |
| 369 | return self |
| 370 | |
| 371 | def insert_after(self, tree: dict) -> "Zipper": |
| 372 | """ |
| 373 | Insert a new subtree after the focus node (as right sibling in binary tree), |
| 374 | it becomes the next of the focus node, returning a new zipper. |
| 375 | |
| 376 | Args: |
| 377 | tree (dict): The new subtree to insert |
| 378 | |
| 379 | Returns: |
| 380 | Zipper: A new zipper with the inserted subtree |
| 381 | """ |
| 382 | # Edge Case: Handle when already at root (no breadcrumbs) |
| 383 | if not self.breadcrumbs: |
| 384 | # Can't insert after root, return self |
| 385 | return self |
| 386 | |
| 387 | # Get the last breadcrumb |
| 388 | last_breadcrumb = self.breadcrumbs[-1] |
| 389 | parent = last_breadcrumb["parent"] |
| 390 | is_left = last_breadcrumb["is_left"] |
| 391 | |
| 392 | # If we're the left child, we can insert a right sibling |
| 393 | # If we're the right child, we can't insert after us in a binary tree |
| 394 | if is_left: # We're the left child |
| 395 | # Create a new parent with the inserted tree as right child |
| 396 | new_parent = { |
| 397 | "value": parent["value"], |
| 398 | "left": self.tree, |
| 399 | "right": tree |
| 400 | } |
| 401 | |
| 402 | # Update the breadcrumb trail |
| 403 | new_breadcrumbs = self.breadcrumbs[:-1] |
| 404 | |
| 405 | # Return a new zipper focused on the same node but with updated parent structure |
| 406 | return Zipper(new_parent, new_breadcrumbs) |
| 407 | else: # We're the right child |
| 408 | # Can't insert after the right child in a binary tree |
| 409 | return self |
| 410 | |
| 411 | def delete(self) -> "Zipper | None": |
| 412 | """ |
| 413 | Removes the focus node and all subtrees, focus moves to the |
| 414 | next node if possible otherwise to the prev node if possible, |
| 415 | otherwise to the parent node, returning a new zipper. |
| 416 | |
| 417 | Returns: |
| 418 | Zipper | None: A new zipper with focus relocated, or None if tree becomes empty |
| 419 | """ |
| 420 | # Edge Case: Handle when already at root (no breadcrumbs) |
| 421 | if not self.breadcrumbs: |
| 422 | # Deleting root node results in empty tree |
| 423 | return None |
| 424 | |
| 425 | # Get the last breadcrumb |
| 426 | last_breadcrumb = self.breadcrumbs[-1] |
| 427 | parent = last_breadcrumb["parent"] |
| 428 | is_left = last_breadcrumb["is_left"] |
| 429 | |
| 430 | # Try to move to next sibling first |
| 431 | next_sibling = self.next() |
| 432 | if next_sibling is not None: |
| 433 | # Create a new parent with the current node removed |
| 434 | if is_left: |
| 435 | new_parent = { |
| 436 | "value": parent["value"], |
| 437 | "left": None, |
| 438 | "right": parent.get("right") |
| 439 | } |
| 440 | else: |
| 441 | new_parent = { |
| 442 | "value": parent["value"], |
| 443 | "left": parent.get("left"), |
| 444 | "right": None |
| 445 | } |
| 446 | |
| 447 | # Update breadcrumbs with new parent |
| 448 | new_breadcrumbs = self.breadcrumbs[:-1] + [{ |
| 449 | "parent": new_parent, |
| 450 | "is_left": next_sibling.breadcrumbs[-1]["is_left"] if next_sibling.breadcrumbs else False |
| 451 | }] |
| 452 | |
| 453 | return Zipper(next_sibling.tree, new_breadcrumbs) |
| 454 | |
| 455 | # Try to move to prev sibling |
| 456 | prev_sibling = self.prev() |
| 457 | if prev_sibling is not None: |
| 458 | # Create a new parent with the current node removed |
| 459 | if is_left: |
| 460 | new_parent = { |
| 461 | "value": parent["value"], |
| 462 | "left": None, |
| 463 | "right": parent.get("right") |
| 464 | } |
| 465 | else: |
| 466 | new_parent = { |
| 467 | "value": parent["value"], |
| 468 | "left": parent.get("left"), |
| 469 | "right": None |
| 470 | } |
| 471 | |
| 472 | # Update breadcrumbs with new parent |
| 473 | new_breadcrumbs = self.breadcrumbs[:-1] + [{ |
| 474 | "parent": new_parent, |
| 475 | "is_left": prev_sibling.breadcrumbs[-1]["is_left"] if prev_sibling.breadcrumbs else False |
| 476 | }] |
| 477 | |
| 478 | return Zipper(prev_sibling.tree, new_breadcrumbs) |
| 479 | |
| 480 | # Move to parent |
| 481 | parent_zipper = self.up() |
| 482 | if parent_zipper is not None: |
| 483 | # Remove the current node from parent |
| 484 | if is_left: |
| 485 | return parent_zipper.set_left(None) |
| 486 | else: |
| 487 | return parent_zipper.set_right(None) |
| 488 | |
| 489 | # This shouldn't happen, but just in case |
| 490 | return None |
| 491 | |
| 492 | # Handled Edge Cases: None tree input, None left/right children, Already at root for up() |