Skill 6: Recursion with Trees (Pyret)
1. Designing Tree Data Structures
What to Teach
Trees are recursive data structures where nodes can have multiple self-referential fields. Unlike lists (which have one "next" reference), trees branch into multiple subtrees.
Basic Tree Structure
data BinaryTree:
| leaf(value :: Number)
| node(value :: Number, left :: BinaryTree, right :: BinaryTree)
end
Tree Construction
# simple tree with just leaves
simple-tree = node(5, leaf(3), leaf(7))
# more complex tree
complex-tree = node(10,
node(5, leaf(2), leaf(8)),
node(15, leaf(12), leaf(20)))
Teaching Examples
Good Example:
data FamilyTree:
| person(name :: String, age :: Number, children :: List<FamilyTree>)
end
grandchild1 = person("Emma", 5, empty)
grandchild2 = person("Lily", 7, empty)
child1 = person("Alice", 30, [list: grandchild1, grandchild2])
child2 = person("Bob", 32, empty)
parent = person("Carol", 55, [list: child1, child2])
Alternative Tree Structure:
data FileSystem:
| file(name :: String, size :: Number)
| folder(name :: String, contents :: List<FileSystem>)
end
documents = folder("Documents",
[list: file("report.txt", 1024),
file("data.csv", 2048)])
pictures = folder("Pictures",
[list: file("vacation.jpg", 5120)])
root = folder("Home", [list: documents, pictures])
What to Point Out:
- Tree nodes contain data plus references to subtrees
- Leaf nodes (base cases) have no further tree references
- Trees can be binary (two children) or n-ary (any number of children)
- Self-referential fields enable the recursive structure
- Tree depth can vary at different branches
Common Student Mistakes to Watch For
-
Confusing tree structure with lists
# BAD - trying to use list operations on trees
my-tree.first
my-tree.rest -
Wrong data definition structure
# BAD - not properly self-referential
data BadTree:
| leaf(value :: Number)
| node(value :: Number, left :: Number, right :: Number)
end
2. Basic Tree Traversal with Cases
What to Teach
Tree functions use cases to handle different node types, recursing on all self-referential fields to process the entire tree.
Standard Tree Recursion Template
fun tree-function(tree :: TreeType) -> ReturnType:
doc: "description of what function does"
cases(TreeType) tree:
| leaf(value) => base-case-with-value
| node(value, left, right) =>
combine(value, tree-function(left), tree-function(right))
end
where:
tree-function(leaf(value)) is base-case-with-value
tree-function(node(value, leaf(left-val), leaf(right-val))) is combine(value, base-case-with-left-val, base-case-with-right-val)
end
Teaching Examples
Simple Example - Tree Size:
fun tree-size(tree :: BinaryTree) -> Number:
doc: "counts total number of nodes in tree"
cases(BinaryTree) tree:
| leaf(value) => 1
| node(value, left, right) =>
1 + tree-size(left) + tree-size(right)
end
where:
tree-size(leaf(5)) is 1
tree-size(node(10, leaf(5), leaf(15))) is 3
tree-size(node(10, node(5, leaf(2), leaf(8)), leaf(15))) is 5
tree-size(node(1, leaf(2), node(3, leaf(4), leaf(5)))) is 5
end
Simple Example - Tree Sum:
fun tree-sum(tree :: BinaryTree) -> Number:
doc: "adds all values in tree"
cases(BinaryTree) tree:
| leaf(value) => value
| node(value, left, right) =>
value + tree-sum(left) + tree-sum(right)
end
where:
tree-sum(leaf(5)) is 5
tree-sum(node(10, leaf(5), leaf(15))) is 30
tree-sum(node(10, node(5, leaf(2), leaf(8)), leaf(15))) is 40
tree-sum(node(1, leaf(-2), leaf(3))) is 2
end
Simple Example - Tree Height:
fun tree-height(tree :: BinaryTree) -> Number:
doc: "finds maximum depth of tree"
cases(BinaryTree) tree:
| leaf(value) => 1
| node(value, left, right) =>
1 + num-max(tree-height(left), tree-height(right))
end
where:
tree-height(leaf(5)) is 1
tree-height(node(10, leaf(5), leaf(15))) is 2
tree-height(node(10, node(5, leaf(2), leaf(8)), leaf(15))) is 3
tree-height(node(1, leaf(2), node(3, node(4, leaf(5), leaf(6)), leaf(7)))) is 4
end
What to Point Out:
- Each case handles a different tree structure
- Leaf case provides base case (no further recursion)
- Node case recurses on ALL subtree fields
- Results from recursive calls are combined appropriately
- Multiple recursive calls happen in node case
Common Student Mistakes to Watch For
-
Forgetting to recurse on all subtrees
# BAD - only recursing on left subtree
fun bad-tree-sum(tree):
cases(BinaryTree) tree:
| leaf(value) => value
| node(value, left, right) => value + bad-tree-sum(left)
end
end -
Wrong base case handling
# BAD - not handling leaf values properly
fun bad-tree-size(tree):
cases(BinaryTree) tree:
| leaf(value) => 0 # should be 1
| node(value, left, right) => 1 + bad-tree-size(left) + bad-tree-size(right)
end
end -
Incorrect combination of results
# BAD - wrong operation for height
fun bad-tree-height(tree):
cases(BinaryTree) tree:
| leaf(value) => 1
| node(value, left, right) =>
1 + tree-height(left) + tree-height(right) # should use max, not +
end
end
3. Trees with Variable Children
What to Teach
Not all trees are binary. Trees can have any number of children, typically represented using lists. This requires recursing over lists of subtrees.
N-ary Tree Structure
data GeneralTree:
| leaf(value :: Number)
| node(value :: Number, children :: List<GeneralTree>)
end
Recursion on List of Trees
fun sum-tree-list(trees :: List<GeneralTree>) -> Number:
doc: "sums all trees in a list"
cases(List) trees:
| empty => 0
| link(first-tree, rest-trees) =>
tree-sum(first-tree) + sum-tree-list(rest-trees)
end
where:
sum-tree-list(empty) is 0
sum-tree-list(link(leaf(5), empty)) is 5
sum-tree-list(link(leaf(3), link(leaf(7), empty))) is 10
sum-tree-list(link(node(10, empty), link(leaf(5), empty))) is 15
end
fun tree-sum(tree :: GeneralTree) -> Number:
doc: "sums all values in general tree"
cases(GeneralTree) tree:
| leaf(value) => value
| node(value, children) => value + sum-tree-list(children)
end
where:
tree-sum(leaf(5)) is 5
tree-sum(node(10, empty)) is 10
tree-sum(node(10, link(leaf(3), link(leaf(7), empty)))) is 20
tree-sum(node(5, link(node(2, link(leaf(1), empty)), link(leaf(3), empty)))) is 11
end
Teaching Examples
Complex Example - File System:
data FileSystem:
| file(name :: String, size :: Number)
| folder(name :: String, contents :: List<FileSystem>)
end
fun total-size-list(items :: List<FileSystem>) -> Number:
cases(List) items:
| empty => 0
| link(first, rest) => total-size(first) + total-size-list(rest)
end
where:
total-size-list(empty) is 0
total-size-list(link(file("test.txt", 100), empty)) is 100
total-size-list(link(file("a.txt", 50), link(file("b.txt", 75), empty))) is 125
total-size-list(link(folder("docs", empty), link(file("c.txt", 25), empty))) is 25
end
fun total-size(fs :: FileSystem) -> Number:
doc: "calculates total size of files and folders"
cases(FileSystem) fs:
| file(name, size) => size
| folder(name, contents) => total-size-list(contents)
end
where:
total-size(file("test.txt", 100)) is 100
total-size(folder("empty", empty)) is 0
total-size(folder("docs", link(file("a.txt", 50), link(file("b.txt", 75), empty)))) is 125
total-size(folder("nested", link(folder("sub", link(file("c.txt", 25), empty)), empty))) is 25
end
fun find-large-files(fs :: FileSystem, min-size :: Number) -> List<String>:
doc: "finds all files larger than min-size"
fun find-in-list(items :: List<FileSystem>) -> List<String>:
cases(List) items:
| empty => empty
| link(first, rest) =>
first-results = find-large-files(first, min-size)
rest-results = find-in-list(rest)
first-results + rest-results
end
end
cases(FileSystem) fs:
| file(name, size) =>
if size >= min-size: [list: name] else: empty end
| folder(name, contents) => find-in-list(contents)
end
where:
find-large-files(file("small.txt", 50), 100) is empty
find-large-files(file("large.txt", 150), 100) is [list: "large.txt"]
find-large-files(folder("empty", empty), 100) is empty
find-large-files(folder("docs", link(file("big.txt", 200), link(file("tiny.txt", 10), empty))), 100) is [list: "big.txt"]
find-large-files(folder("nested", link(folder("sub", link(file("huge.txt", 500), empty)), link(file("medium.txt", 150), empty))), 100) is [list: "huge.txt", "medium.txt"]
end
What to Point Out:
- N-ary trees require helper functions for processing lists
- Recursion happens both on trees and on lists of trees
- Pattern combines tree recursion with list recursion
- Helper functions handle the list processing separately
Common Student Mistakes to Watch For
-
Trying to recurse directly on list without helper
# BAD - can't recurse on list directly in tree function
fun bad-tree-sum(tree):
cases(GeneralTree) tree:
| node(value, children) => value + tree-sum(children) # children is a list
end
end -
Forgetting to process all children
# BAD - only processing first child
fun bad-process(tree):
cases(GeneralTree) tree:
| node(value, children) =>
if children.length() > 0:
value + bad-process(children.first)
else:
value
end
end
end
Common Teaching Scenarios
When Students Ask "How is this different from list recursion?"
"Lists have one 'next' link, so you recurse once. Trees have multiple branches, so you might recurse on two, three, or more subtrees. You need to handle and combine all those results."
When Students Forget to Handle All Subtrees
"Look at your data definition. How many fields refer back to the tree type? You need one recursive call for each of those fields."
When Students Struggle with N-ary Trees
"When you have a list of trees, you need two kinds of traversal: tree recursion for individual trees, and some list processing for the children. It's easiest to make two separate functions that call each other. The tree one must be recursive, whereas the list one can be recursive, or could use a for each loop."
When Students Get Confused About Base Cases
"What's the simplest tree? Usually it's a leaf with just data and no subtrees. That's where recursion stops, just like empty lists in list recursion."