Your concept feed

Let’s picture it

Let’s start with three stops.

🏠 Home

🌳 Park

☕ Café

Home. Then the park. Then the café. Just a few things in a row.

Swipe when you’re ready

One little change

Point to the middle one.

0 · Home

1 · Park

2 · Café

The park is second. In Python, its position is 1, because counting starts at 0.

Same idea. One more small step.

Now it has a name

That’s a list.

Home

Park

Café

A list keeps things in order. An index is just a position in that list.

Want to try a tiny question?

No pressure. Just try it.

Which place is at position 0?

You can also keep scrolling

1 / 4

Start small

One small step at a time.

Nothing to learn first. Let’s replay this little example.

Let’s start with three stops.

🏠 Home

🌳 Park

☕ Café

Home. Then the park. Then the café. Just a few things in a row.

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

stops = ["home", "park", "cafe"]
assert stops[1] == "park"
assert len(stops) == 3

A small step before this topic

Let’s picture it

Now visit each stop.

Home

Park

Café

You don’t need three different instructions. “Visit the next place” works each time.

Swipe when you’re ready

One little change

One, then the next.

✓ Home

Park

Café

Finish home. Move to the park. Then do the same at the café.

Same idea. One more small step.

Now it has a name

That repeat is a loop.

✓ Home

✓ Park

✓ Café

One small action, repeated for each item. Three stops mean three visits.

Want to try a tiny question?

No pressure. Just try it.

Add one more stop. How many visits now?

You can also keep scrolling

1 / 4

Start small

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Let’s start with three stops.

🏠 Home

🌳 Park

☕ Café

Home. Then the park. Then the café. Just a few things in a row.

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

visited = []
for stop in ["home", "park", "cafe"]:
    visited.append(stop)
assert visited == ["home", "park", "cafe"]

A small step before this topic

Let’s picture it

What if it rains?

☔ Rain

☕ Café

Let’s choose the café on rainy days, and the park on sunny days.

Swipe when you’re ready

One little change

Today is sunny.

☀ Sun

🌳 Park

The rule stays the same. The weather changed, so we choose the other place.

Same idea. One more small step.

Now it has a name

That’s an if / else.

Raining?

Yes: café

No: park

A condition is a yes-or-no question. Its answer chooses which step happens next.

Want to try a tiny question?

No pressure. Just try it.

It’s raining. Where does our rule send us?

You can also keep scrolling

1 / 4

Start small

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Now visit each stop.

Home

Park

Café

You don’t need three different instructions. “Visit the next place” works each time.

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

raining = True
if raining:
    next_stop = "cafe"
else:
    next_stop = "park"
assert next_stop == "cafe"

A small step before this topic

Let’s picture it

Name a tiny job.

3

add one

4

Our job is “add one.” Give it 3, and it gives back 4.

Swipe when you’re ready

One little change

Try a new input.

8

add one

9

Give the same job 8. It gives back 9. We can reuse the instructions.

Same idea. One more small step.

Now it has a name

That job is a function.

input

function

answer

Input goes in. An answer comes back. In Python, return sends the answer back.

Want to try a tiny question?

No pressure. Just try it.

What does add-one return for 5?

You can also keep scrolling

1 / 4

Start small

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

What if it rains?

☔ Rain

☕ Café

Let’s choose the café on rainy days, and the park on sunny days.

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

def add_one(number):
    return number + 1

assert add_one(3) == 4
assert add_one(8) == 9

A small step before this topic

Let’s picture it

Picture a pile of plates.

Pink · top

Blue · bottom

Blue goes down first. Pink goes on top.

Swipe when you’re ready

One little change

Take the top one.

Take pink

Blue stays

Pink comes off first, even though blue arrived first.

Same idea. One more small step.

Now it has a name

That’s a stack.

Newest call

Earlier call

Last in, first out. Paused function calls work this way too: finish the newest call, then return.

Want to try a tiny question?

No pressure. Just try it.

Add green on top. Which plate comes off next?

You can also keep scrolling

1 / 4

Start small

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Name a tiny job.

3

add one

4

Our job is “add one.” Give it 3, and it gives back 4.

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

plates = []
plates.append("blue")
plates.append("pink")
assert plates.pop() == "pink"
assert plates == ["blue"]

A small step before this topic

Let’s picture it

Now picture a line of people.

Ana

Bo

Ana arrives first. Bo waits behind her.

Swipe when you’re ready

One little change

Ana goes first.

Ana leaves

Bo

Cy joins

Bo moves to the front. New arrivals join the back.

Same idea. One more small step.

Now it has a name

That’s a queue.

front →

Bo

Cy

First in, first out. Unlike plates, we serve the oldest waiting item first.

Want to try a tiny question?

No pressure. Just try it.

Who goes before Cy?

You can also keep scrolling

1 / 4

Start small

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Picture a pile of plates.

Pink · top

Blue · bottom

Blue goes down first. Pink goes on top.

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

from collections import deque

line = deque(["Ana", "Bo"])
assert line.popleft() == "Ana"
assert list(line) == ["Bo"]

A small step before this topic

Let’s picture it

Have we visited the park?

Home ✓

Park ✓

Keep a little checklist of places we’ve seen.

Swipe when you’re ready

One little change

Write park again.

Home ✓

Park ✓

We still only need one check beside park. We’re remembering whether, not how many times.

Same idea. One more small step.

Now it has a name

That’s a set.

park in seen?

Yes

A set keeps distinct items. “Is park in here?” becomes a quick membership check.

Want to try a tiny question?

No pressure. Just try it.

Add park twice. How many copies in a set?

You can also keep scrolling

1 / 4

Start small

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Let’s start with three stops.

🏠 Home

🌳 Park

☕ Café

Home. Then the park. Then the café. Just a few things in a row.

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

seen = set()
seen.add("park")
seen.add("park")
assert "park" in seen
assert len(seen) == 1

A small step before this topic

Let’s picture it

Let’s remember a little more.

Park

5 minutes

The park is five minutes away. Write that beside its name.

Swipe when you’re ready

One little change

Look it up later.

“park”

notebook

5

Ask for “park.” The notebook gives you 5. No need to measure the walk again.

Same idea. One more small step.

Now it has a name

That’s a dictionary.

key: park

value: 5

A key finds a value. Here, the place name is the key and the time is the value.

Want to try a tiny question?

No pressure. Just try it.

We now write park: 6. What does park return?

You can also keep scrolling

1 / 4

Start small

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Have we visited the park?

Home ✓

Park ✓

Keep a little checklist of places we’ve seen.

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

minutes = {"park": 5, "cafe": 8}
assert minutes["park"] == 5
minutes["park"] = 6
assert minutes["park"] == 6

A small step before this topic

Let’s picture it

Draw our little walk.

Home

Park

Café

A dot for each place. A line where we can walk directly.

Swipe when you’re ready

One little change

Two short walks can join.

Home

Park

Café

Home to park, then park to café. We can reach the café without a direct road.

Same idea. One more small step.

Now it has a name

Dots and links have names.

node

edge

node

A dot is a node. A link is an edge. Together, they make a graph.

Want to try a tiny question?

No pressure. Just try it.

Must two places share a direct road to be reachable?

You can also keep scrolling

1 / 4

Start small

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Let’s start with three stops.

🏠 Home

🌳 Park

☕ Café

Home. Then the park. Then the café. Just a few things in a row.

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

neighbors = {"home": ["park"], "park": ["home", "cafe"], "cafe": ["park"]}
assert "park" in neighbors["home"]
assert "cafe" in neighbors["park"]

A small step before this topic

Let’s picture it

Where did we put the book?

Cup

Plate

Book

Pen

Try “second shelf, first box.” We need two positions, not just one.

Swipe when you’re ready

One little change

Pick a row, then a column.

0,0

0,1

1,0

1,1

Python calls the second row 1. The first column is 0. So the book is at [1][0].

Same idea. One more small step.

Now it has a name

That’s a two-dimensional table.

cupboard

row

column

Two labels find one cell. A third label could tell us which cupboard contains the table.

Want to try a tiny question?

No pressure. Just try it.

Two cupboards have the same shelves. What extra label helps?

You can also keep scrolling

1 / 4

Start small

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Let’s start with three stops.

🏠 Home

🌳 Park

☕ Café

Home. Then the park. Then the café. Just a few things in a row.

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

shelves = [["cup", "plate"], ["book", "pen"]]
assert shelves[1][0] == "book"
assert shelves[0][1] == "plate"

A small step before this topic

The foundations

Let’s picture it

Same door. One small difference.

You + key

Locked door

You have a key. Your friend doesn’t. The door is the same, but your next move isn’t.

Swipe when you’re ready

One little change

Remember the key.

at door

has key?

If we only write down “at the door,” we lose something important.

Same idea. One more small step.

Now it has a name

That little note is a state.

place

key: yes

A state remembers what we need to continue. Here: where we are, and whether we have the key.

Want to try a tiny question?

No pressure. Just try it.

Is “at the door” enough to decide if we can enter?

You can also keep scrolling

1 / 4

The foundations

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

What if it rains?

☔ Rain

☕ Café

Let’s choose the café on rainy days, and the park on sunny days.

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

def can_enter(cell, tokens_left):
    return cell == "." or tokens_left > 0

assert can_enter("#", 1)
assert not can_enter("#", 0)

A small step before this topic

The foundations

Let’s picture it

How many little jobs?

Hi

Visit three places. Say hello once at each. That’s three hellos.

Swipe when you’re ready

One little change

Now try every pair.

3 people

× 3 greetings

= 9

Three people each greet all three people, including themselves for this toy count. That’s nine greetings.

Same idea. One more small step.

Now it has a name

Count how the work grows.

one pass: n

all pairs: n²

One pass grows with n. Trying every pair grows with n × n. Code length doesn’t tell us that.

Want to try a tiny question?

No pressure. Just try it.

With 4 items, how many ordered pairs, including self-pairs?

You can also keep scrolling

1 / 4

The foundations

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Same door. One small difference.

You + key

Locked door

You have a key. Your friend doesn’t. The door is the same, but your next move isn’t.

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

def predecessor_checks(n):
    return sum(i for i in range(n))

assert predecessor_checks(5) == 10
assert predecessor_checks(1000) == 499500

A small step before this topic

The foundations

Let’s picture it

Find 8 in a sorted row.

2

4

6

8

10

Start with 2, 4, 6, 8, 10. Look at the middle: 6.

Swipe when you’re ready

One little change

Keep the side that can work.

2 ×

4 ×

6 ×

8

10

8 is bigger than 6. Everything on the left is too small, so we can leave it behind.

Same idea. One more small step.

Now it has a name

Keep one promise.

8

10

If 8 is present, it stays in the part we keep. That repeating promise is called an invariant.

Want to try a tiny question?

No pressure. Just try it.

Would this left-or-right shortcut work on an unsorted row?

You can also keep scrolling

1 / 4

The foundations

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

How many little jobs?

Hi

Visit three places. Say hello once at each. That’s three hellos.

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

def lower_bound(values, target):
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if values[mid] >= target:
            hi = mid
        else:
            lo = mid + 1
    return lo

assert lower_bound([2, 4, 4, 9], 4) == 1
assert lower_bound([2, 4, 4, 9], 10) == 4
assert lower_bound([], 3) == 0

A small step before this topic

Recursion

Let’s picture it

Open a box.

Big box

Small box

Empty

There’s a smaller box inside. We already know how to open a box.

Swipe when you’re ready

One little change

Do the same small job again.

Big box

Small box

Empty

Open the smaller box. Keep going until there isn’t another box inside.

Same idea. One more small step.

Now it has a name

That’s the idea of recursion.

smaller

stop

A function asks itself to handle a smaller case. The empty box is our stopping point: the base case.

Want to try a tiny question?

No pressure. Just try it.

What if every box contains another box forever?

You can also keep scrolling

1 / 4

Recursion

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Same door. One small difference.

You + key

Locked door

You have a key. Your friend doesn’t. The door is the same, but your next move isn’t.

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

def suffix_sum(values):
    def total(i):
        if i == len(values):
            return 0
        return values[i] + total(i + 1)
    return total(0)

assert suffix_sum([4, 2, 7]) == 13
assert suffix_sum([]) == 0

Let’s picture it

Count a tiny family of dots.

Parent

Child: 1

One parent has two children. Each child says, “There’s one of me.”

Swipe when you’re ready

One little change

Let the answers travel up.

Total: 3

1

The parent adds the two answers, then counts itself: 1 + 1 + 1.

Same idea. One more small step.

Now it has a name

That works for bigger trees too.

my answer

left answer

right answer

Ask each child about its little tree. Combine the answers. You don’t need to hold the whole tree in your head.

Want to try a tiny question?

No pressure. Just try it.

Do we also count the parent itself?

You can also keep scrolling

1 / 4

Trees

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Open a box.

Big box

Small box

Empty

There’s a smaller box inside. We already know how to open a box.

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

def height(node):
    if node is None:
        return 0
    _, left, right = node
    return 1 + max(height(left), height(right))

tree = (8, (3, None, None), (10, None, (12, None, None)))
assert height(tree) == 3
assert height(None) == 0

Let’s picture it

How far down is this dot?

Level 0

Level 1

Call the top dot level 0. Its children sit one level below.

Swipe when you’re ready

One little change

Send a little note downward.

My level: 1

Your level: 2

Tell each child: “Your level is my level plus one.”

Same idea. One more small step.

Now it has a name

Some answers need the parent’s help.

send level ↓

child

A child can count its descendants. But its distance from the top needs information from above.

Want to try a tiny question?

No pressure. Just try it.

Can a leaf tell its level just by seeing no children?

You can also keep scrolling

1 / 4

Trees

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Count a tiny family of dots.

Parent

Child: 1

One parent has two children. Each child says, “There’s one of me.”

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

def has_sum(node, remaining):
    if node is None:
        return False
    value, left, right = node
    remaining -= value
    if left is None and right is None:
        return remaining == 0
    return has_sum(left, remaining) or has_sum(right, remaining)

tree = (8, (3, None, None), (10, None, None))
assert has_sum(tree, 11)
assert not has_sum(tree, 8)
assert not has_sum(None, 0)

Let’s picture it

Two trees can make different promises.

8

3

10

In a search tree, smaller keys go left and larger keys go right. We’ll use distinct keys here.

Swipe when you’re ready

One little change

A heap promises something else.

3

10

8

A min-heap keeps the smallest value at the top. Its left and right sides need not be sorted.

Same idea. One more small step.

Now it has a name

Choose the promise you need.

find a key

take smallest

Looking for an ordered key? Think search tree. Repeatedly taking the smallest? Think min-heap.

Want to try a tiny question?

No pressure. Just try it.

Does a min-heap promise its left side is smaller than its right?

You can also keep scrolling

1 / 4

Trees

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Find 8 in a sorted row.

2

4

6

8

10

Start with 2, 4, 6, 8, 10. Look at the middle: 6.

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

from heapq import heappop, heappush

pending = []
for cost in [8, 2, 7, 1]:
    heappush(pending, cost)
assert pending[0] == 1
assert [heappop(pending) for _ in range(4)] == [1, 2, 7, 8]

Let’s picture it

Visit the same three dots.

A

B

C

We can say the parent’s name first, then visit its children.

Swipe when you’re ready

One little change

Or wait until the children finish.

Finish last: A

First: B

Then: C

For a count, the parent needs the children’s answers first. So visit B, C, then finish A.

Same idea. One more small step.

Now it has a name

The timing has a name.

before

between

after

Parent first is preorder. Children first is postorder. Left, parent, right is inorder for a binary tree.

Want to try a tiny question?

No pressure. Just try it.

Which timing helps combine child answers?

You can also keep scrolling

1 / 4

Trees

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Count a tiny family of dots.

Parent

Child: 1

One parent has two children. Each child says, “There’s one of me.”

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

def traversal_orders(root):
    preorder, inorder, postorder = [], [], []
    def visit(node):
        if node is None:
            return
        value, left, right = node
        preorder.append(value)
        visit(left)
        inorder.append(value)
        visit(right)
        postorder.append(value)
    visit(root)
    return preorder, inorder, postorder

tree = (2, (1, None, None), (3, None, None))
assert traversal_orders(tree) == ([2, 1, 3], [1, 2, 3], [1, 3, 2])
assert traversal_orders(None) == ([], [], [])

Let’s picture it

A grandparent’s rule still counts.

8

3

10

Everything in 8’s left subtree must stay below 8, not just its immediate child.

Swipe when you’re ready

One little change

A local check can miss trouble.

8 → left

3 → right

9: too big

Put 9 to the right of 3, but still inside 8’s left subtree. It passes 3’s rule and breaks 8’s.

Same idea. One more small step.

Now it has a name

Carry the allowed range.

below 8

above 3

3 < key < 8

Pass down the lower and upper limits from ancestors. Each node must fit all the rules that brought us here.

Want to try a tiny question?

No pressure. Just try it.

Is checking only a node and its immediate children enough?

You can also keep scrolling

1 / 4

Trees

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Two trees can make different promises.

8

3

10

In a search tree, smaller keys go left and larger keys go right. We’ll use distinct keys here.

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

def valid_bst(node, low=float("-inf"), high=float("inf")):
    if node is None:
        return True
    value, left, right = node
    if not low < value < high:
        return False
    return valid_bst(left, low, value) and valid_bst(right, value, high)

invalid = (10, (5, None, (12, None, None)), None)
assert not valid_bst(invalid)
assert valid_bst((10, (5, None, None), (12, None, None)))
assert not valid_bst((10, (10, None, None), None))
assert valid_bst(None)

Let’s picture it

Walk upward from two dots.

A

B

C

B and C have the same parent, A. Their upward paths meet there.

Swipe when you’re ready

One little change

Find the first meeting place.

Meet here: A

B ↑

C ↑

We want the lowest shared ancestor, not an older ancestor farther up.

Same idea. One more small step.

Now it has a name

Let the children report what they found.

two sides meet

found B

found C

If the two targets are found on different sides, this parent is their meeting place. Assume both targets exist.

Want to try a tiny question?

No pressure. Just try it.

Could one target itself be the shared ancestor?

You can also keep scrolling

1 / 4

Trees

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Count a tiny family of dots.

Parent

Child: 1

One parent has two children. Each child says, “There’s one of me.”

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

def common_ancestor(node, a, b):
    if node is None:
        return None
    value, left, right = node
    if value == a or value == b:
        return value
    left_result = common_ancestor(left, a, b)
    right_result = common_ancestor(right, a, b)
    if left_result is not None and right_result is not None:
        return value
    return left_result if left_result is not None else right_result

tree = (1, (2, (4, None, None), (5, None, None)), (3, None, None))
assert common_ancestor(tree, 4, 5) == 2
assert common_ancestor(tree, 4, 3) == 1
assert common_ancestor(tree, 2, 4) == 2

A familiar idea

Walking upward one parent at a time works.

node

parent

grandparent

But thousands of ancestor queries can repeat the same long climbs. Let’s save shortcuts.

Swipe when you’re ready

One new wrinkle

Save jumps that double.

2 links

4 links

For every node, remember its ancestor 1, 2, 4, 8… links above. Two 2-link jumps make one 4-link jump.

Same idea. One more small step.

Try a tiny example

Six links become four plus two.

start

up 4

up 2

To climb six parents, take one saved four-link jump, then one saved two-link jump.

Same idea. One more small step.

Notice what matters

Build the next row from the previous.

half jump

double jump

up[j][v] is the 2ʲ-th ancestor. Its value is up[j−1][up[j−1][v]], unless that intermediate ancestor is missing.

Same idea. One more small step.

Make it reusable

This is binary lifting.

prepare once

answer many

Precompute a table once. Queries combine logarithmically many jumps. The same shortcuts also speed up repeated lowest-common-ancestor queries.

Want to try a tiny question?

No pressure. Just try it.

What should happen when a jump would pass above the root?

You can also keep scrolling

1 / 6

Trees

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Walk upward from two dots.

A

B

C

B and C have the same parent, A. Their upward paths meet there.

1 / 3

Python for Kth Ancestor of a Tree Node. The complete example includes small checks you can run; the full notes state its scope.

Show the complete Python solution

class TreeAncestor:
    def __init__(self, parent):
        self.n = len(parent)
        self.up = [list(parent)]
        for _ in range(1, max(1, self.n.bit_length())):
            previous = self.up[-1]
            self.up.append([
                -1 if previous[v] == -1 else previous[previous[v]]
                for v in range(self.n)
            ])

    def get_kth(self, node, k):
        if not 0 <= node < self.n or k < 0:
            raise ValueError("Need a valid node and nonnegative k")
        if k >= self.n:
            return -1
        bit = 0
        while k and node != -1:
            if k & 1:
                node = self.up[bit][node]
            k >>= 1
            bit += 1
        return node

tree = TreeAncestor([-1, 0, 1, 2, 3, 4, 5])
assert tree.get_kth(6, 6) == 0
assert tree.get_kth(6, 7) == -1
assert tree.get_kth(3, 0) == 3

Let’s picture it

Join the two longest arms.

A

B

C

A path through A can come from B and leave toward C.

Swipe when you’re ready

One little change

But send only one arm upward.

send one ↑

left arm

right arm

To extend this path to A’s parent, choose one side. Taking both would create a fork, not a path.

Same idea. One more small step.

Now it has a name

Keep two different answers.

return one arm

compare two arms

Return one extendable arm. Separately remember the best complete path seen anywhere. That longest path is the tree’s diameter.

Want to try a tiny question?

No pressure. Just try it.

Can a simple path use three arms at one node?

You can also keep scrolling

1 / 4

Trees

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Count a tiny family of dots.

Parent

Child: 1

One parent has two children. Each child says, “There’s one of me.”

1 / 3

No need to read the code yet. It’s here when you want to connect the picture to Python.

Show the Python example

def diameter(root):
    longest = 0
    def height(node):
        nonlocal longest
        if node is None:
            return 0
        _, left, right = node
        left_height = height(left)
        right_height = height(right)
        longest = max(longest, left_height + right_height)
        return 1 + max(left_height, right_height)
    height(root)
    return longest

tree = (1, (2, (4, None, None), (5, None, None)), (3, None, None))
assert diameter(tree) == 3
assert diameter((1, None, None)) == 0
assert diameter(None) == 0

Let’s picture it

BST order does not guarantee small height.

1

2

3

Inserting 1,2,3 into an ordinary BST creates a chain. Search becomes linear.

Swipe when you’re ready

One little change

Store a height summary.

left height

right height

balance

After each insertion, recompute height and compare left versus right. Difference beyond one means this node is unbalanced.

Same idea. One more small step.

Now it has a name

Rotate without breaking order.

2 root

1 left

3 right

For 1→2→3, rotate left at 1. Node 2 becomes the root with 1 left and 3 right.

Want to try a tiny question?

No pressure. Just try it.

What does a rotation preserve?

You can also keep scrolling

1 / 4

Trees

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Two trees can make different promises.

8

3

10

In a search tree, smaller keys go left and larger keys go right. We’ll use distinct keys here.

1 / 3

Python for AVL tree: rebalance local height. The complete example includes small checks you can run; the full notes state its scope.

Show the complete Python solution

class AVLNode:
    def __init__(self, key):
        self.key, self.left, self.right, self.height = key, None, None, 1

def height(node): return node.height if node else 0

def refresh(node):
    node.height = 1 + max(height(node.left), height(node.right))

def rotate_left(root):
    top, middle = root.right, root.right.left
    top.left, root.right = root, middle
    refresh(root); refresh(top)
    return top

def rotate_right(root):
    top, middle = root.left, root.left.right
    top.right, root.left = root, middle
    refresh(root); refresh(top)
    return top

def avl_insert(root, key):
    if root is None: return AVLNode(key)
    if key < root.key: root.left = avl_insert(root.left, key)
    elif key > root.key: root.right = avl_insert(root.right, key)
    else: return root
    refresh(root)
    balance = height(root.left)-height(root.right)
    if balance > 1:
        if key > root.left.key: root.left = rotate_left(root.left)
        return rotate_right(root)
    if balance < -1:
        if key < root.right.key: root.right = rotate_right(root.right)
        return rotate_left(root)
    return root

root = None
for key in [1,2,3,4,5]: root = avl_insert(root, key)
assert root.key == 2 and root.height == 3
assert root.left.key == 1 and root.right.key == 4

Let’s picture it

Values alone do not preserve shape.

1 with left 2

1 with right 2

Trees root-left and root-right can both visit values 1,2 but have different topology.

Swipe when you’re ready

One little change

Record missing children.

1

null

2

Level order with null markers distinguishes where absent links occur. Trim only trailing nulls that add no shape information.

Same idea. One more small step.

Now it has a name

Restore parents in queue order.

parent

left token

right token

Read two child tokens for each queued real parent, creating nodes only for non-null values.

Want to try a tiny question?

No pressure. Just try it.

Why are null markers needed?

You can also keep scrolling

1 / 4

Trees

One small step at a time.

This idea builds on these smaller ones. Pick any to revisit it here.

Visit the same three dots.

A

B

C

We can say the parent’s name first, then visit its children.

1 / 3

Python for Serialize and restore a binary tree. The complete example includes small checks you can run; the full notes state its scope.

Show the complete Python solution

from collections import deque

class TreeNode:
    def __init__(self, value):
        self.value, self.left, self.right = value, None, None

def serialize(root):
    if root is None: return []
    output, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        if node is None: output.append(None)
        else:
            output.append(node.value); queue.extend((node.left,node.right))
    while output and output[-1] is None: output.pop()
    return output

def deserialize(values):
    if not values: return None
    root, queue, i = TreeNode(values[0]), deque(), 1
    queue.append(root)
    while queue and i < len(values):
        parent = queue.popleft()
        if values[i] is not None:
            parent.left = TreeNode(values[i]); queue.append(parent.left)
        i += 1
        if i < len(values) and values[i] is not None:
            parent.right = TreeNode(values[i]); queue.append(parent.right)
        i += 1
    return root

root = TreeNode(1); root.right = TreeNode(2); root.right.left = TreeNode(3)
assert serialize(root) == [1,None,2,3]
assert serialize(deserialize(serialize(root))) == [1,None,2,3]