SUNY Geneseo Department of Computer Science

Recurrence Relations for Tree Traversals

{Date}

CSci 141, Fall 2003
Prof. Doug Baldwin

Return to List of Lectures

Previous Lecture

Misc

Lab available in lab sessions tomorrow

Exam 2 next Wednesday (Nov. 19)

Lists and Trees
Rules and format similar to exam 1

Questions?

Recurrence relations and "display"

    display()
        if ( ! this.isEmpty() )
            print this.root()
            this.left().display()
            this.right().display()

Number of primitive tree messages

Recurrence relation:

f(0) = 1
f(n) = 4 + f(n1) + f(n2) if n > 0
where n1 + n2 = n-1

Won't usually be n-1 nodes on one side and n-2 on other

Because n-1 + n-2 = 2n - 3
Total number of nodes in subtrees = n-1

Look for a pattern in f(n):

n		f(n)
0		1
1		4+f(0)+f(0) = 4 + 1 + 1
2		4 + f(1) + f(0)
		= 4 + 4 + 1 + 1 + 1
3		4 + f(n1) + f(n2)
	a)	4 + f(2) + f(0)
		= 4 + 4 + 4 + 1 + 1 + 1 + 1
	b)	4 + f(1) + f(1)
		= 4 + 4 + 1 + 1 + 4 + 1 + 1
		= 4 + 4 + 4 + 1 + 1 + 1 + 1

f(n) = 4n + (n+1) ?

Prove by strong induction on n

Base case: n=0
- f(0) = 1 from recurrence
- = 4*0 + (0+1) [i.e., closed form]
Induction step:
- Assume f(x) = 4x + (x+1) for all natural numbers x < k
- Show f(k) = 4k + (k+1)
  - f(k) = 4 + f(n1) + f(n2) [recurrence]
  - = 4 + (4n1 + (n1+1)) + (4n2 + (n2+1))
    - [ n1 + n2 = k-1, n1 and n2 natural, imply n1 < k & n2 < k; induction hypothesis applies]
  - = 4 + 4(n1 + n2) + (n1 + n2) +1+1
  - = 4( (k-1) + 1) + ( (k-1) +1) +1
    - [ Since n1 + n2 = k-1 ]
  - = 4k + ( k +1)

Due date for Lab 11 extended to Thursday, 11/13, so people can incorporate this idea into the other recurrences if they wish.

Next

Tree traversals