SUNY Geneseo Department of Computer Science

Recursive Tree Algorithms

Previous Lecture

Example Tree Algorithm

Count the nodes in a tree:

    // In some subclass of OrderedTree...
    int count()
        if ( ! this.isEmpty() )
            int n = 1 + this.getLeft().count()
            return n + this.getRight().count()
        else
            return 0

Correctness?

• By induction on number of nodes, n
• Base Case: n = 0
  • isEmpty succeeds, algorithm returns 0 (which matches the number of nodes, n)
• Induction hypothesis: (Strong induction) for all m < k, k > 0, count sent to an m-node tree returns m
• Induction: show that count sent to a k-node tree returns k.
  • Tree not empty, so isEmpty fails
  • 1 + this.getLeft().count() is number of nodes for root plus left subtree (left subtree correctly counted according to induction hypothesis, since it has fewer than k nodes)
  • Adding this.getRight().count() adds nodes from right subtree (again, correctly counted per induction hypothesis)
  • Yields the number of nodes in the whole tree, k

Performance?

• Count executions of "if" statement as representative operation
• f(n) = number of times "if" is executed to count nodes in an n-node tree
  • f(n) = 1 if n = 0
  • f(n) = 1 + f(k) + f(n-k-1) if n > 0
    • where k is the number of nodes in the left subtree, k <= n-1
• Tabulate some values
  • f(0) = 1
  • f(1) = 1 + f(0) + f(0) = 3
  • f(2) = 1 + f(1) + f(0) = 5
  • f(3) = 1 + f(1) + f(1) = 7
    • or 1 + f(2) + f(0) = 7
• Notice that value of f() seems not to depend on choice of k -- maybe this is always true, in which case recurrence could be rewritten as
  • f(n) = 1 if n = 0
  • f(n) = 1 + f(0) + f(n-1) = 2 + f(n-1) if n > 0
• This recurrence is easy to solve as a "kn+c" one: f(n) = 2n + 1
• But since the second recurrence itself came from a guess about k not mattering in the original, we still need to prove that 2n + 1 is a correct closed form for the original recurrence
  • By induction on n
  • Base case: n = 0
    • f(0) = 1 = 2 * 0 + 1
  • Induction hypothesis (strong induction again): f(m) = 2m + 1 for all m < x, x> 0
  • Show f(x) = 2x + 1
    • f(x) = 1 + f(k) + f(x-k-1)
    • = 1 + (2k+1) + (2(x-k-1)+1)
    • = 1 + 2k + 1 + 2x - 2k -2 +1
    • = 2x + 1

Next

Ordered Tree Properties

Read Section 13.3

Next Lecture