FOR PMY 1733 ONLY

hw1.docx

CS 211 Homework #1

Please complete the homework problems on the following page using a separate piece of paper. Note that this is an individual assignment and all work must be your own. Be sure to show your work when appropriate. This assignment is due in lab on Monday, October 10, 2016.

1. [3] Given the following pre-order and in-order traversals, reconstruct the appropriate binary tree. NOTE: You must draw a single tree that works for both traversals.

Pre-order: A, E, D, G, B, F, I, C

In-order: D, E, B, G, A, F, I, C

2. [3] Starting with an empty BST, draw each step in the following operation sequence. Assume that all removals come from the left subtree when the node to remove is full.

Insert(5), Insert(10), Insert(2), Insert(9), Insert(1), Insert(3), Remove(5).

3. [3] Starting with an empty BST, draw each step in the following operation sequence. Assume that all removals come from the right subtree when the node to remove is full.

Insert(10), Insert(5), Insert(23), Insert(4), Insert(19), Insert(7), Insert(9), Insert(6), Remove(5).

4. Given the following binary tree:

A. [1] What is the height of the tree?

B. [1] What is the depth of node 90?

C. [1] What is the height of node 90?

D. [3] Give the pre-order, in-order, and post-order traversal of this tree.

5. Given the following two functions:

int f(int n) { if(n <= 0) { Return 0; } return 1 + f(n - 1); }

int g(int n) { int sum = 0; for(int i = 0; i < n; i++) { sum += 1; } Return sum; }

A. [2] State the runtime complexity of both f() and g()

B. [2] State the memory complexity for both f() and g()

C. [4] Write another function called "int h(int n)" that does the same thing but has a more efficient runtime complexity.

image1.png