Day 23 - More trees

Skills: None

Pre-reading: 7.1.3, 7.1.4

Intro (20 mins)

• Yesterday we saw binary trees where each node has exactly two children. Today we explore n-ary trees where nodes can have any number of children.
• Real-world example: an organization chart, where each employee has a name, title, and a (possibly empty) list of direct reports.
• Tables struggle to represent nested relationships naturally—it's hard to find all indirect reports or the depth of the organization.
• Data Definition:

  import lists as L
  data OrgTree:
    | node(name :: String, title :: String, reports :: List<OrgTree>)
  end
  
  # Example: A small organization
  alex-tree = node("Alex", "Engineer", [list: ])
  casey-tree = node("Casey", "Engineer", [list: ])
  jordan-tree = node("Jordan", "CTO", [list: alex-tree, casey-tree])
  riley-tree = node("Riley", "Accountant", [list: ])
  taylor-tree = node("Taylor", "CFO", [list: riley-tree])
  avery-tree = node("Avery", "CEO", [list: jordan-tree, taylor-tree])

• Example: Check if someone is a leaf (has no reports):

  fun is-leaf(t :: OrgTree) -> Boolean:
    cases (OrgTree) t:
      | node(name, title, reports) => L.empty(reports)
    end
  where:
    is-leaf(alex-tree) is true
    is-leaf(avery-tree) is false
  end

• Unlike binary trees, n-ary trees usually require mutually recursive functions—one function processes a single tree, another processes a list of trees -- the latter is what is called on the children, and calls back to the former.
• Example: Count all employees in the organization:

  fun count-employees(t :: OrgTree) -> Number:
    cases (OrgTree) t:
      | node(name, title, reports) => 1 + count-employees-list(reports)
    end
  end
  
  fun count-employees-list(ts :: List<OrgTree>) -> Number:
    cases (List) ts:
      | empty => 0
      | link(first, rest) => count-employees(first) + count-employees-list(rest)
    end
  where:
    count-employees(alex-tree) is 1
    count-employees(avery-tree) is 6
  end

Class Exercises (35 mins)

• Design a function all-titles that returns a list of all titles in the organization tree (duplicates are okay). You'll need both all-titles and all-titles-list functions.
• Design a function count-by-title that takes an OrgTree and a title string, and returns the number of employees with that title.
• Design a function find-employee that takes an OrgTree and a name, and returns the OrgTree node for that employee (or a special value if not found).
• Design a function org-height that returns the number of levels in the organization tree (root is level 1).
• Design a function promote-all that takes an OrgTree and a function from String -> String, and returns a new tree where every title has been updated by the function.
• Design a function flatten-names that returns a list of all employee names in the organization (pre-order traversal).
• Design a function count-reports that takes an OrgTree and a name, and returns how many people report directly to that employee.

Wrap-up (5 mins)

• N-ary trees represent hierarchical data where nodes can have any number of children.
• Processing n-ary trees requires mutually recursive functions—one for single trees, one for lists of trees.
• The same patterns (counting, transforming, searching) apply to n-ary trees as binary trees.