CS14 Assignment 3

Posted: May 13^th, 2002

Due: May 23^rd, 2001

Trees

1. Binary trees

a. What is the maximum possible height of a tree with n nodes?

b. What is the minimum possible height of a tree with n nodes?

c. What is the maximum possible number of nodes in a binary tree of height h?

d. What is the minimum possible number of nodes in a binary tree of height h?

e. Arrange the numbers 2, 4, 6, 9, 12, 14, 18 into a tree of height 3

f. Arrange the same numbers into a tree of height 6

2. Show the result of traversing the following tree

6

/ \

2 7

/ \ \

1 4 9

/ \

3 5

a. Preorder

b. Inorder

c. Posorder

3. Binary search trees

a. Insert the following numbers into a binary search tree, in this order:

8, 16, 12, 14, 18, 11, 6, 4, 7, 5, 13, 15

b. Show the tree after deleting 4

c. Show the tree after deleting 16

4. A level-order traversal of a tree prints out the nodes of the tree by row, and within each row from left to right. For example, a level-order traversal of the tree in question 2 would be

6, 2, 7, 1, 4, 9, 3, 5.

Describe a scheme for performing a level-order traversal of a binary tree. Assume the data contained in the nodes are integers. Would your scheme also work for general trees?

Hint: you will need to use another data structure

Recurrences

5. Solve the following recurrence relations:

a. T(1) = 1

T(n) = T(n-1) + 2

b. T(1) = 1

T(n) = T(n/2) + 1

c. T(1) = 1

T(n) = T(n/2) + n

d. (Bonus)

T(1) = 2

T(n) = 2T(n/2) + 2n