Day 24 - More trees

Advanced Tree Processing: Traversals and Transformations

Duration: 1 Hour

1. Introduction (10 minutes)

• Overview:
  • Recap the recursive OrgTree datatype and a basic recursive function (org-size).
  • Explain that trees are non-linear structures, so simple linear loops (like for each) aren’t enough for traversals or transformations.
• Learning Goals:
  • Understand different orders of traversing trees.
  • See how to write recursive functions that “flatten” a tree into a list.
  • Discuss how to transform a tree by reconstructing its structure.
• Do Now:
  • Ask: “When traversing a tree, in what order could we visit nodes? (e.g., pre-order, post-order, in-order, level-order)”
  • Brief discussion.

2. Traversing Trees Recursively (20 minutes)

• Pre-Order Traversal:
  • Definition: Visit the current node, then recursively traverse each subordinate.
  • Example Function – flatten-org:

    fun flatten-org(t :: OrgTree) -> List<String>:
      cases (OrgTree) t:
        | node(n, title, reports) =>
          # Pre-order: include current node’s name first, then flatten the reports list.
          [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
  • Interactive Exercise:
    • Ask: “What is the output of flatten-org(alice-tree) (using the tree from previous lecture) in pre-order?”
• Discussion:
  • Compare pre-order to other orders (e.g., post-order, level-order).
  • Emphasize that the recursive structure dictates the traversal order.

3. Transforming Trees (20 minutes)

• Why For Each Loops Don’t Work on Trees:
  • Explain that for each loops require linear data (lists) because they process elements one after another.
  • Trees, by contrast, have branching structure. To traverse or transform a tree, you must reconstruct its structure recursively.
• Example Function – Transforming Titles to Uppercase (transform-titles):
  • Task: Produce a new OrgTree in which each node’s title is converted to uppercase.
  • Code:

    fun transform-titles(t :: OrgTree) -> OrgTree:
      cases (OrgTree) t:
        | node(n, title, reports) =>
          node(n, string-to-upper(title), transform-titles-list(reports))
      end
    end
    
    fun transform-titles-list(ts :: List<OrgTree>) -> List<OrgTree>:
      cases (List) ts:
        | empty => empty
        | link(first, rest) => link(transform-titles(first), transform-titles-list(rest))
      end
    end
  • Interactive Exercise:
    • Ask: “What is the output of transform-titles(alice-tree)? How does the structure remain the same?”
• Discussion:
  • Emphasize that recursive functions let us rebuild the tree’s structure as we process each node.
  • Ask: “If we wanted to traverse a tree linearly (say, to compute the sum of all employee ages), what traversal order might we choose?”

4. Wrap-Up (10 minutes)

• Summary:
  • Recap that trees are inherently non-linear, so for linear traversal (flattening) or transformation, recursion is essential.
  • Discuss the different traversal orders and the idea of reconstructing tree structure during transformation.