SUNY Geneseo Department of Computer Science

The Height and Size of Binary Trees

{Date}

CSci 141, Fall 2003
Prof. Doug Baldwin

Misc

Abbreviated office hours tomorrow (2:30 - 3:30)

Worst-case time for binary tree search is Theta(h), where h is height of tree

How does number of items (n) relate to height (h)?

Mini-assignment
Height = number of levels, each recursion in search goes down one level
Binary search follows one branch through tree, so most items in tree are never encountered
Try some examples...

[Trees of Height 3 and Different Numbers of Items]

Largest number of elements for a given height

[Full Height h Tree Has 2 Height h-1 Subtrees]

Or recurrence relation
- S(h) = size of tree as function of height
- S(h) = 0 if h = 0
- S(h) = 1 + 2S(h-1) if h > 0
S(h) = 2^h - 1
- Base case h = 0:
  - S(0 ) = 0 = 1 - 1 = 2⁰ - 1
- Induction step:
  - Assume S(k-1) = 2^k-1 - 1
  - Is S(k) = 2^k - 1?
  - S(k) = 1 + 2S(k-1)
  - = 1 + 2( 2^k-1 - 1)
  - = 1 + 2^k - 2
  - = 2^k - 1
So n = 2^h - 1
How about h as a function of n, so search time can be writtten in terms of n
- n = 2^h - 1
  - Logarithm is inverse of exponentiation
  - i.e., log_bx = p where b^p = x
- n+1 = 2^h
- log₂(n+1) = h
Search time = Theta(h)
- = Theta(log₂(n+1))
- = Theta(log n)
vs search time for a list of Theta(n)

Fewest elements for a given height

[Tree with One Node Per Level]

So searching a tree has a number of cases

Worst Worst case = Theta(n)
- Not finding what it seeks
- Totally unbalanced tree
Best worst case = Theta(log n)
- Not finding what it seeks
- Perfectly balanced, full, tree
Best case = Theta(1)