← Back to course
Code Crew G5 / Week 10 / Wednesday
3/6
Week 10 · Trees

Wednesday

Count the crew
// The fleet command tree
⏱ about 15 min

Wednesday: Count the crew

Mission Control asks how many crew are in the fleet. Rocket starts writing loops inside loops.

"One loop for the leads, one loop for their crew," he says. "But what if a pilot gets their own crew someday?"

Raven points at Bo's part of the tree. "What do you notice about counting Bo's team?"

"It is the same job as counting the whole fleet!" Rocket says. "Just a smaller tree."

Nova glows. "Here is a hint. Count yourself, then ask each child to count their own tree."

Counting with recursion

fleet = {
    "name": "Ada",
    "crew": [
        {"name": "Bo", "crew": [
            {"name": "Cy", "crew": []},
            {"name": "Dee", "crew": []},
        ]},
        {"name": "Eve", "crew": [
            {"name": "Fen", "crew": []},
            {"name": "Gil", "crew": []},
            {"name": "Hal", "crew": []},
        ]},
    ],
}

def count(node):
    total = 1
    for child in node["crew"]:
        total = total + count(child)
    return total

print(count(fleet))
Output:
8
  • Each node counts itself as 1.
  • Then it adds the count of each child's smaller tree.
  • For a leaf, crew is empty, so the loop does not run. A leaf returns 1. That is the base case.
CallReturns
count(Cy)1
count(Dee)1
count(Bo)1 + 1 + 1 = 3
count(Fen), count(Gil), count(Hal)1 each
count(Eve)?
count(Ada)1 + 3 + count(Eve) = 8
What does count(Eve) return?
A new pilot, Ivy, joins Cy's crew. What would count(fleet) return now?
THINK ABOUT COUNT.
  • Read the question.
  • Tap your answer.
Why does a leaf return 1 without calling count again?
Who returns their count to Ada?

Practice lab: count the ship

ship = {
    "name": "Ship",
    "parts": [
        {"name": "Deck A", "parts": [
            {"name": "Lab", "parts": []},
            {"name": "Dock", "parts": []},
        ]},
        {"name": "Deck B", "parts": [
            {"name": "Bridge", "parts": []},
            {"name": "Hold", "parts": []},
        ]},
    ],
}

def count(node):
    total = 1
    for part in node["parts"]:
        total = total + count(part)
    return total

print(count(ship))
print(count(ship["parts"][0]))
print(count(ship["parts"][0]["parts"][0]))
What does the first print line show?
What does the second print line show?
What does the third print line show?
A room called Scope is added inside Lab. What would count(ship) return?
COUNT CHECK
  • Read the question.
  • Tap your answer.
What does count return for any leaf?
How many times is count called in all for count(ship)?
Which calls return their counts to the Ship call?
StatementTrue or false?
count(ship["parts"][1]) returns 3.?
count needs a separate if line for leaves.?
The empty parts list works like a base case.?
count works on the fleet if parts is changed to crew.?
WHY THIS EXERCISEThe empty list of children stops the recursion by itself.
What does count(fleet["crew"][0]) return for the fleet tree?
WHY THIS EXERCISEBo counts 1, plus 1 each for Cy and Dee.

Brilliant! One short function counts any tree, no matter how deep. Tomorrow we print the tree with indents.

← Tuesday