Day 23 - Trees as recursive data

NOTE: should not start with an n-ary tree. Should start with simple binary tree. Maybe back in L22, would resolve that issue as well.

1. Introduction (10 minutes)

• Overview:
  • Recap the limitations of tables for tree data.
  • Return to the idea of recursive data: data defined in terms of themselves (like lists!)
• Our New Example: Organization Tree
  • We will represent an organization’s hierarchy as a tree.
• Learning Goals:
  • Define a recursive datatype for the organization.
  • See how the structure (node plus subtrees) suggests a recursive approach.
• Do Now:
  • Ask: “What parts does an organizational node have? (e.g., name, title, subordinates)”
  • Brief discussion.

2. Defining a Recursive Datatype for Organization Trees (20 minutes)

• Data Definition:
  • Present a new datatype called OrgTree:

    data OrgTree:
      | node(name :: String, title :: String, reports :: List<OrgTree>)
    end
  • Explain that each node has a name, title, and a list of subordinate nodes.
• Creating Examples:
  • Build a simple organization tree:

    # Example: A small organization
    dave-tree = node("Dave", "Engineer", empty)
    frank-tree = node("Frank", "Engineer", empty)
    bob-tree = node("Bob", "CTO", [list: dave-tree, frank-tree])
    eve-tree = node("Eve", "Accountant", empty)
    carol-tree = node("Carol", "CFO", [list: eve-tree])
    alice-tree = node("Alice", "CEO", [list: bob-tree, carol-tree])
• Discussion:
  • Compare this recursive representation to the flat table.
  • Ask: “How does this datatype make it easier to answer questions like ‘How many employees are under Bob?’ or ‘What is the organizational depth?’”

3. Discovering Recursive Functions on Trees (20 minutes)

• Observation:
  • Notice that an OrgTree node consists of a value (name and title) and a list of subtrees.
  • The recursive nature of lists (as we saw earlier) applies here too.
• Example Function – Counting Nodes (org-size):
  • Walk Through Examples:
    • For a tree with no reports, size is 1.
    • For a tree with reports, size is 1 (for the current node) plus the sizes of each subtree.
  • Code via Recursion:

    fun org-size(t :: OrgTree) -> Number:
      cases (OrgTree) t:
        | node(n, title, reports) =>
          1 + org-size-list(reports)
      end
    end
    
    # Helper function: recursively compute the size of a list of OrgTree nodes
    fun org-size-list(ts :: List<OrgTree>) -> Number:
      cases (List) ts:
        | empty => 0
        | link(first, rest) => org-size(first) + org-size-list(rest)
      end
    end
• Interactive Exercise:
  • Ask students: “Trace org-size(alice-tree). What is the total number of nodes (employees)?”
• Discussion:
  • Emphasize how the recursive structure of the datatype guided the function design.
  • Ask: “What similarities do you see between processing lists recursively and processing trees?”

4. Wrap-Up and Reflection (10 minutes)

• Summary:
  • Reinforce that recursive data types (like OrgTree) naturally capture hierarchical relationships.
  • The same recursive template used for lists (handling base cases and recursive cases) can be extended to trees.
• Exit Ticket:
  • Each student writes one sentence explaining why a recursive representation is better for hierarchical data than a table.
• Preview Next Lecture:
  • “Next, we’ll delve deeper into tree traversal and transformation, and discuss why simple linear iteration (like for each loops) does not work on trees.”