Assignment 1, due Aug 27
Part of
the homework for 22C:60, Fall 2004
|
Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list! All assignments will be due at the start of class on the day indicated, and unless there is what insurance companies call "an act of God" - something outside your control; the only exceptions to this rule will be by advance arrangement.
a) How many leaves are there in a complete binary tree with n internal nodes?
b) Give the algorithm, using any programming languag or pseudo-code that approximates a programming language, for traversal of a binary tree, assuming that each vertex has a left child and a right child. Your code should apply the operation bang to each leaf of the tree, defined as a node with no children at all, and half-bang to internal nodes with just one child (left or right).