Trees, Binary Search Trees, and Heaps

Quiz Section Review Problems

CSE326, Summer 2000

1. Show that the maximum number of nodes in a binary tree of height h is .

2. A full node is a node with two children. Prove that the number of full nodes plus one is equal to the number of leaves in a nonempty binary tree.

3. Write a routine to print the nodes of a binary tree in level-order. List the root, then nodes at depth 1, followed by nodes at depth 2, and so on.

4. Write a function to print the nodes in a binary tree in ascending order of key fields.

5. Show the result of inserting 3, 1, 4, 6, 9, 2, 5, 7 into an initially empty binary search tree.

6. Write a function to test the equality of two binary trees.

bool equal(tree_pointer t1, tree_pointer t2);

7. Write a function swap_tree that takes a binary tree and swaps the left and right children of every node.

8. Given the input of size N, fill out the running time for each of the operations associated with a particular ADT. Consider the worst case of each operation. For Delete, assume you have been given a reference to some particular element.

9. Answer the following heap questions:

 a. Show the result of inserting 10, 12 , 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, and 2, one at a time, into an initially empty binary min-heap.

b. Show the result of using the linear-time algorithm to build a binary heap using the same input.

c. Show the result of performing three deleteMin operations in the heap built by (b).

d. What are the time complexities for heap operations such as insert, delete, decreaseKey, increaseKey, remove, and buildHeap.

e. Can both insert and findMin be implemented in constant time?

10. Write efficient functions that take only a pointer to the root of a binary tree, T, and compute:

a.       The number of nodes in T.

b.      The number of leaves in T.

c.       The number of full nodes in T.