Introduction To Program Design Lecture 18:

What It Means

An arbitrary-arity node may receive any number of recursive answers. Built-in list operations combine them: all for universal Boolean questions, any for existential questions, and fold for custom summaries.

The current node's answer must also be combined with the child answers.

Read, Run, and Change

Predict the output, then select Run code. Edit the example and run it again to test your prediction. Reset restores the original program. Each example runs independently.

Try itGive a child a label longer than 12 characters and run again.

Run codeResetEditable Kotlin

1

fun allLabelsShort(item: MenuItem): Boolean {

2

    return item.label.length <= 12 &&

3

    item.children.all(::allLabelsShort)

4

}

5

​

6

fun main() {

7

    val drinks = MenuItem("Drinks", listOf(

8

        MenuItem("Tea", emptyList()),

9

        MenuItem("Juice", emptyList())

10

    ))

11

    println(allLabelsShort(drinks))

12

}

Supporting code included with this example

These definitions are loaded automatically each time you run. The editable program above supplies this example's inputs.

MenuItem.kt
data class MenuItem(val label: String, val children: List<MenuItem>)

Check the original program's output

true

The current label must be short, and every child subtree must satisfy the same property. On a leaf, all over the empty children list returns true.

Notice: Separate the current-node question from the child-tree combination.

Supplementary and External Resources

Practice

  1. What combines the current and child answers?

  2. Which operation combines all child trees?

  3. What does children.all return for a leaf?

What It Means

A Set is a collection without duplicate equal elements. Tree queries can return Sets when the question asks for unique labels, categories, or other repeated facts.

Set union with + combines answers while automatically removing duplicates.

Read, Run, and Change

Predict the output, then select Run code. Edit the example and run it again to test your prediction. Reset restores the original program. Each example runs independently.

Every label must be nonempty because first() selects its first character.

Try itAdd Toast beside Tea. Does the result contain T twice?

Run codeResetEditable Kotlin

1

fun allInitials(item: MenuItem): Set<Char> {

2

    val mine = setOf(item.label.first())

3

    return item.children.fold(mine) { found, child ->

4

        found + allInitials(child)

5

    }

6

}

7

​

8

fun main() {

9

    val drinks = MenuItem("Drinks", listOf(

10

        MenuItem("Tea", emptyList()),

11

        MenuItem("Juice", emptyList())

12

    ))

13

    println(allInitials(drinks))

14

}

Supporting code included with this example

These definitions are loaded automatically each time you run. The editable program above supplies this example's inputs.

MenuItem.kt
data class MenuItem(val label: String, val children: List<MenuItem>)

Check the original program's output

[D, T, J]

The accumulator starts with the current initial. Each child contributes a Set, and union keeps only one copy of repeated characters.

Notice: Choose List when order and duplicates matter; choose Set when uniqueness is the intended meaning.

Supplementary and External Resources

Practice

  1. Can a Set contain the same Char twice?

  2. What is the fold accumulator type?

  3. What operator combines Sets here?

What It Means

A course site can contain many modules, a folder can contain many files, and a family member can have many descendants. These structures cannot assume that every item has exactly two children.

This shape appears in web navigation, document models, organizational data, and game worlds. Learning to process every child prepares students for problems where the amount of branching is determined by the data itself.

Read This Example

A model to think with

Course site
Module 1
  Reading A
  Reading B
  Practice
Module 2

One module may have three direct children while another has none. A program that displays or searches the site needs to visit however many children actually exist.

Notice: The number of children is part of the information, not a fixed property of the program.

Supplementary and External Resources

Practice

  1. Why is a course site a many-child hierarchy?

  2. Name another structure with an unpredictable number of children.

  3. What must a traversal do for each item?