SUNY Geneseo Department of Computer Science

Tree Traversals, Part 2

Return to List of Lectures

Misc

SOFIs

• On-line
• Now through May 2
• Check e-mail or see https://www.onlinecourseevaluations.com/login.aspx?s=geneseo

Lab 11 (tree height) due today

• Written report

Questions?

Tree Traversals

Process (e.g., print) all nodes in a tree

    // In class BinaryTree<E>
    private E root
    private BinaryTree<E> left, right

    traverse() {
        if ( ! this.isEmpty() ) {
            left.traverse()                   n1 elements
            process root                      constant time
            right.traverse()                  n2 elements
        }
    }

• n₁ + n₂ = n - 1

Kinds of traversal

• Preorder = root before children
• Inorder = root between children
• Postorder = root after children

Section 13.3.2

• Basics of traversals
• Proofs that traversal algorithm really works
• Visits every node
• Never visits a node twice
• Therefore traverse makes exactly n visits for n-node tree, so Θ(n) time

Can you do a more rigorous derivation of execution time?

• Recurrence
  • C(n) = 0 if n = 0
  • C(n) = C(n₁) + C(n₂) + 1 if n > 0 where n₁ + n₂ = n - 1 and n₁, n₂ ≥ 0
• Patterns
  • C(0) = 0
  • C(1) = C(0) + C(0) + 1 = 1
  • C(2) = C(0) + C(1) + 1 = 2
    • or C(1) + C(0) + 1 = 2
• Prove C(n) = n, by induction on n
  • Base case, n = 0, C(0) = 0 from recurrence
  • Induction hypothesis: assume C(j) = j, for all 0 ≤ j < k
  • Show C(k) = k
    • C(k) = C(k₁) + C(k₂) + 1, k₁ + k₂ = k - 1
    • = k₁ + k₂ + 1 by induction hypothesis
    • = k - 1 + 1
    • = k

Uses of traversals

• Pre-order: push information down tree
• In-order: to process ordered trees in order
• Post-order: pull information up a tree (e.g., height)

Lab

Hand out Lab 12

Dictionary data structure

• Translates keys into values
• Search, insert, delete
• Implemented by lists, ordered trees, hash tables, etc.

Next

Priority queues and heaps

Read...

• Section 14.4 intro (pp 493 bottom to 494)
• 14.4.1 (pg 494)
• 14.4.4 up to but not including "Insertion" (pp 497 bottom to 500 top)