Frequently Asked Questions about HW5

A.
No balance is necessary, you just have to maintain the binary search tree order.

A.
We don't need them in numerical account number order, we just want them in pre-order.

Sometimes in-order isn't the most useful order. For example, if you were to write out the elements of a tree in in-order and then regenerate the tree from that list, you'd get a very unbalanced tree.

A.
It should create a CDT, initialize its root pointer, and give back an ADT for that CDT. Don't do anything like open the file and read it there, that's not generic (i.e., some trees might not have associated files). Opening and reading the file should be done in the main program.

A.
Some operations for a binary search tree can be done without recursion, since you often just need to go left or right at each step (and not both). These can be done with iteration, although you can use recursion if you like.

Some operations do require backtracking, like printing out the whole tree. There you'll need to use recursion unless you choose to add a parent pointer to nodes (we did leave that type open to you). I'd recommend against using parent pointers, since it means students have to successfully maintain another pointer for each node. (Feel free to use a parent pointer in one of your functions--this just refers to parent pointers as part of a node, i.e., like left and right.)

So, you have some flexibility in these issues. For your own practice, I'd recommend that you do at least one tree function with iteration and at least one with recursion.

A.
The fact that TreePrint only takes a FILE * and not a string (for a filename) implies the answer.

A.
To the screen, since accounts.out does not get generated until the program quits. So, it means you have to run the program and the first option you should perform is your "print the tree" option.

In summary, students may have different accounts.out files, but the print of the tree right after the program starts will have the same values for everyone since you all read from the same accounts.in file.

A.
We don't yet know how to write a data structure like that, i.e., so that it could deal with anything. Just assume the key is something that can be compared with <, ==, etc.

A.
Hard-coding is fine.

A.
You have to for a data structure that is designed with ADTs/CDTs when you use recursion. They are not necessary otherwise in this assignment.

A.
That's correct, you can't use TreeFind as a helper for TreeDelete since it only returns an element pointer. (We still, of course, need to implement TreeFind since it is required for people using a tree.)

So, what you need is a helper function that returns a node pointer--you could use something like that to help implement both. Keep in mind, of course, that you may also need access to a parent when adding, removing, etc. though.

Finally, as an alternative, you can always repeat finding-like code in each tree function that needs to find something.

A.
Don't do that, that's overkill (and for a future homework).

A.
You can do the same thing we did when we deleted from a linked list (see that lab). With recursion, return the left (or right) pointer that the parent should be pointing to (to the previous recursive call). With iteration, maintain a parent pointer as you advance the current pointer.

A.
TreePrint and PrintElement take FILE *'s for the file to print to. So, they expect pointers to files that are already open--you should not be opening files in those functions.

In TreePrint and PrintElement, you only have to print to the file that is passed to the function. That file pointer could be for standard input OR some opened file.

I.e., the main program will send standard input to TreePrint for the "print the tree operation" and it will pass the opened "accounts.out" file to TreePrint when that is needed.

A.
You have to change the type of the key and value in your tree module to fit what the test program uses as a key and value (as the documentation in the test program says).

A.
Sure.

A.
Free every node. Also, you must free the CDT.

A.
That's fine. Just make sure you free all the nodes in the cut-off subtree after their elements are re-added. We don't want extra nodes floating around.

There are other valid methods for deletion as well.

A.
It's because the pointer parameter to your helper function is always a copy of the pointer that is passed to it (i.e., it's a copy of tree->root, or later, some left or right pointer). So, when you change that copy, you do not change the original.

Either pass in a "pointer to a pointer" or pass back "who the parent should be pointing to" to the previous call (for a recursive solution). It's similar to what we did with deleting from a linked list.

Or, if you write your TreeAdd function iteratively, you can put all the code in one function and not have to worry about passing copies to some helper function.