← Back to course
Code Crew G5 / Week 10 / Friday
5/6
Week 10 · Trees

Friday

Leaves and searching
// The fleet command tree
⏱ about 15 min

Friday: Leaves and searching

Two questions arrive from Mission Control. How many crew lead nobody? And is Gil in this fleet?

Rocket cracks his knuckles. "Two new functions. Both trees. Let us build it!"

Raven asks, "What do you notice about a leaf that makes it different from other nodes?"

"Its crew list is empty," Rocket says. "That could be the base case."

Nova blinks. "Here is a hint. For the search, stop as soon as any child says yes."

Counting leaves

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_leaves(node):
    if node["crew"] == []:
        return 1
    total = 0
    for child in node["crew"]:
        total = total + count_leaves(child)
    return total

print(count_leaves(fleet))
Output:
5

A leaf returns 1. Any other node adds up the leaves in its children's trees. It does not count itself.

What does count_leaves return for Bo's node?
What does count_leaves return for Hal's node?

Searching the tree

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 has_member(node, name):
    if node["name"] == name:
        return True
    for child in node["crew"]:
        if has_member(child, name):
            return True
    return False

print(has_member(fleet, "Gil"))
print(has_member(fleet, "Zed"))
Output:
True
False
Statement about has_memberTrue or false?
It checks the node itself before its children.?
It returns False as soon as one child says no.?
has_member(fleet["crew"][0], "Gil") returns True.?
WHY THIS EXERCISEIt may only say False after checking every child, just like linear search.
LOOP OR RECURSION?
  • Read the question.
  • Tap your answer.
Why does recursion fit trees so well?

Practice lab: leaves and a search

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_leaves(node):
    if node["parts"] == []:
        return 1
    total = 0
    for part in node["parts"]:
        total = total + count_leaves(part)
    return total

def has_part(node, name):
    if node["name"] == name:
        return True
    for part in node["parts"]:
        if has_part(part, name):
            return True
    return False

print(count_leaves(ship))
print(has_part(ship, "Hold"))
print(has_part(ship["parts"][0], "Hold"))
What does the first print line show?
What does the second print line show?
What does the third print line show?
What does count_leaves(ship["parts"][1]) return?
TREE FUNCTION CHECK
  • Read the question.
  • Tap your answer.
Does count_leaves count Deck A itself?
What does has_part(ship, "Ship") return?
When can has_part return False?
StatementTrue or false?
count_leaves(ship) and count(ship) give the same number.?
has_part(ship, "Gym") returns False.?
A leaf returns 1 in count_leaves.?
has_part looks inside every smaller tree if it has to.?
WHY THIS EXERCISESmall changes to the same shape answer different questions.
Lab gets a room called Scope. What would count_leaves(ship) return?
WHY THIS EXERCISEOne leaf is lost and one is gained, so the count stays 4.

Week 10 complete! You can store, count, print and search a tree. Next week you plan your capstone project.

← Thursday