SUNY Geneseo Department of Computer Science

Tree Traversal

Previous Lecture

Misc

Exam 2 next Wednesday (Nov. 19)

• Lists and Trees
• Rules and format similar to exam 1
• Practice Questions on the Web

Questions?

Strong Induction and Trees

Count the nodes in a tree:

    int size() {
        if ( this.isEmpty() )
            return 0
        else
            return 1 + this.left().size()
                     + this.right().size()

How many primitive tree messages?

Recurrence relation for messages, f(), in terms of number of nodes, n

• f(n) = 1 if n = 0
• f(n) = 3 + f(n₁) + f(n₂) if n > 0
  • where n₁ + n₂ = n-1

Find a closed form

• Guess f(n) = 3n + (n+1) = 4n + 1

Prove this by strong induction on n

• Base case n = 0
  • f(0) = 1 [from recurrence]
  • = 4 * 0 + 1
• Induction step
  • Induction hypothesis: assume f(x) = 4x + 1 for all x < k, k > 0
  • Show f(k) = 4k + 1
  • f(k) = 3 + f(k₁) + f(k₂),
    • where k₁ + k₂ = k-1
    • [recurrence]
  • = 3 + 4k₁ + 1 + 4k₂ + 1,
    • where k₁ + k₂ = k-1
    • [induction hypothesis]
  • = 5 + 4(k-1)
  • = 5 + 4k - 4
  • = 4k + 1

Traversal

Traversal = visiting every node in a data structure in order to do something with it

e.g., compute a tree's height

Hint: height is precisely defined as follows:

• The height of an empty tree is 0
• The height of a non-empty tree is the maximum of the heights of the subtrees, plus 1

    height()
        if ! this.isEmpty()
            leftHeight = this.left().height()
            rightHeight = this.right().height()
            if leftHeight > rightHeight
                return 1 + leftHeight
            else
                return 1 + rightHeight
        else
            return 0

Mini-assignment: work out efficiency of the above version of "height" vs one that sends "height" messages wherever it needs left or right subtree heights

Postorder traversal - visit subtrees first, then root

Also preorder, in-order

Next

Inserting new items into a binary search tree

Next Lecture