This is course-related, but it is not homework, and I would really appreciate it if someone would answer this.
I suppose the naive method is to say that since there are n nodes, and each node has three fields (BinaryTree left/right and Object key), then the space requirement is 3*S[sub]reference[/sub]*n, but I don’t think that’s right.
Looks right to me. (I’m guessing S[sub]reference[/sub] means size-of reference?)
Hmm, one thing that might or might not be relevant is that you are told there are n internal nodes. Usually, the definition of internal nodes excludes leaf nodes (nodes where both children are null). In a tree with n internal nodes, the number of leaf nodes can range from 1 (the nodes are linked in a chain - no node has two non-null children) to ~n (it’s a balanced binary tree).
Since the problem doesn’t seem to specify the shape of the tree, I would wager that your expression is correct - it seems safe to assume that n is the number of total nodes, not just non-leaf nodes.
That sounds right, if each node has all three fields. However, it’s possible to implement a tree such that branch nodes only hold two pointers (left and right), and leaf nodes only hold one (data).
It’s not common from what I’ve seen, but if you’re really tight on space, you could implement branches and leaves with different classes, derived from a single node class. Even allowing for one extra pointer per node (for the VMT, class info, or whatever your language uses for polymorphism), you’d still save S[sub]reference[/sub] bytes per leaf node.
Yes, S[ref] is the size required for an object reference. Thanks for the help folks.