Day 21 - Intro to Trees

Skills: None

Pre-reading: 7.1.1

TODO expand this -- and maybe don't start with an n-ary tree.

Intro (10 mins)

• Today we introduce trees—a way to represent hierarchical data, where each item can have sub-items.
• Real-world example: an organization chart, where each employee has a name, title, and a (possibly empty) list of direct reports.
• Tables are great for flat data, but struggle to represent nested relationships naturally.
• Example: In a table with columns name, title, manager, it’s easy to find direct reports, but hard to find all indirect reports or the depth of the organization.

Class Exercises (35 mins)

• Given the following table:

  org-table = table: name, title, manager
    row: "Alice", "CEO", ""
    row: "Bob", "CTO", "Alice"
    row: "Carol", "CFO", "Alice"
    row: "Dave", "Engineer", "Bob"
    row: "Eve", "Accountant", "Carol"
    row: "Frank", "Engineer", "Bob"
  end
  1. Direct Reports: Write an expression to find all direct reports of "Bob".
  2. Chain of Command: For "Dave", write an expression to find their manager.
  3. All Reports (Challenge): How would you find all people who report (directly or indirectly) to "Alice"? What makes this hard with just tables?
  4. Tree Structure: Sketch (on paper) how you would represent this organization as a tree, where each node contains a name, title, and a list of direct reports.
  5. Tree Data Definition: Write a Pyret data definition for an OrgTree, where each node has a name, title, and a list of OrgTree direct reports.

Wrap-up (5 mins)

• Tables are powerful for flat data, but trees are better for representing and processing hierarchical structures.
• Next time: we’ll define tree data in code and write functions to process them.