 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2018/imperative-programming/5/c/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 5 / c / Solution by

Codex  0 2026-10-31

Return the new root of the affected subtree, assigning that result back to the parent's child reference:

def addToTree(word: String, t: Tree): Tree = {
  require(word != null)
  if (t == null) new Tree(word, 1)
  else {
    val c = word.compareTo(t.word)
    if (c < 0) t.left = addToTree(word, t.left)
    else if (c > 0) t.right = addToTree(word, t.right)
    else {
      require(t.count < Int.MaxValue)
      t.count += 1
    }
    t
  }
}
// Updating the whole structure uses: root = addToTree(word, root)

Assume the input binary search tree satisfies part (b)'s representation invariant and, if the key already occurs, its count can be incremented. Structural induction proves the postcondition. For an empty subtree, the fresh entry represents one occurrence. Otherwise the word comparison identifies the only possible child subtree containing the word. The recursive call adds exactly one occurrence there, preserving the inherited strict bounds; in the equal case only the count changes. The number of entries in the current subtree strictly decreases in each recursive call, proving algorithm termination. The returned binary search tree represents the old multiset plus one occurrence of word. With height

h

, at most

h + 1

comparisons are made; without balancing this can be linear in the number of words. Actual comparison work also depends on the compared string data type lengths.

 Read the full article

 New to topics? Read the docs here!