#### Introduction

- A perfect maze is a maze in which any two points can be connected by exactly 1 path:
- We can represent these with binary trees:
- The root of the tree is the top right.
- Each node can connect either north or east (but not both).

#### Code (Python)

```
import numpy as np
import random
from maze_functions import *
width = 5
height = 5
grid = np.zeros((width, height, 2), bool)
for j in range(height):
for i in range(width):
if i == width - 1 and j == height - 1:
# top right cell
# can't go east or north
continue
if j == height - 1:
# top cell
# can only go east
goEast = True
elif i == width - 1:
# far right cell
# can't go east
goEast = False
else:
goEast = random.randint(0, 1) == 0
cell = (i, j)
if goEast:
link_cells(grid, cell, east(cell))
else:
link_cells(grid, cell, north(cell))
draw_maze(grid)
```

#### Pros and Cons

- Pros:
- Very fast, runs in O(n) time and space complexity.

- Cons:
- There is a long corridor along the north and east walls.
- A cell cannot be open in both the north and east directions.
- Easy to solve:
- From any cell, you only need to travel either north or east to reach the top right cell.