Day 23 - More trees

Skills: None

Pre-reading: 7.1.3, 7.1.4

Intro (10 mins)

• Trees are recursive, branching data structures. Recall example:

  data OrgTree:
    | node(name :: String, title :: String, reports :: List<OrgTree>)
  end
• Many tree operations involve traversing or transforming the tree recursively.
• Example: Flattening a tree into a list of names (pre-order traversal):

  fun flatten-org(t :: OrgTree) -> List<String>:
    cases (OrgTree) t:
      | node(n, title, reports) =>
        [list: n] + flatten-org-list(reports)
    end
  end
  
  fun flatten-org-list(ts :: List<OrgTree>) -> List<String>:
    cases (List) ts:
      | empty => empty
      | link(first, rest) => flatten-org(first) + flatten-org-list(rest)
    end
  end

Class Exercises (40 mins)

Given the OrgTree data definition and example trees from last class:

1. Post-Order Traversal: Write a function flatten-org-post that returns a list of names in post-order (visit all reports before the current node).
2. Transform Titles: Write a function title-suffix that takes an OrgTree and a string, and returns a new tree where every title has the suffix added (e.g., " (Manager)").
3. Count Leaves: Write a function count-leaves that returns the number of employees with no reports.
4. Replace Name: Write a function replace-name that takes an OrgTree, an old name, and a new name, and returns a new tree with the name replaced everywhere it occurs.
5. Find All Paths: Write a function all-paths that returns a list of lists, where each inner list is the path from the root to a leaf.
6. Level-Order Traversal (Challenge): Write a function flatten-org-level that returns a list of names in level-order (breadth-first).

Wrap-up (5 mins)

• Recursive tree functions let us traverse and transform hierarchical data in many ways.
• Next time: more advanced tree processing and applications.