Week 10: Exercises

1. Odd Delete

Write a procedure that deletes all odd numbers from a linked list of integers.

2. Doubling Every Node

Write a procedure that takes a linked list and inserts a duplicate copy of every node. For example, if the list is 3 → 4 → 6 → nil, it should become 3 → 3 → 4 → 4 → 6→ 6 → nil.

3. No Adjacent Duplicates

Write a procedure that takes a linked list and collapses any adjacent duplicates. In other words, if a series of adjacent nodes in the list have the same value, the procedure should delete all but one of them.

4. Fixed Array-Based Queue

In the lecture we sketched the implementation of a fixed-size queue backed by a fixed-sized array. Implement this.

5. Dynamic Array-Based Queue

In the lecture we also described how to use a resizable array to implement a queue that can grow to any size. Implement this.

6. Random Tree

Write a function randomTree(h: integer): pnode that builds a complete binary tree of height h. Every value in the tree should be a random integer in the range 0 .. 999.

7. Complete Tree

Write a function completeTree(h: integer): pnode that builds a complete binary tree of height h. Every node's value should be that node's depth.

8. Destroy a Tree

Write a procedure destroy(p: pnode) that disposes all nodes in a binary tree.

9. Mirror Image

Write a procedure mirror(var p: pnode) that flips a tree from left to right so that it looks like a mirror image of the original tree.

10. Tree Compare

Write a function equal(p, q: pnode): boolean that returns true if two binary trees are identical, i.e. they have the same structure and the same values in corresponding nodes.

11. Tree Walk

Write a procedure that prints out all values in a binary search tree in increasing order.

12. Largest Product in a Grid

Solve Project Euler's problem 11.