Matthew Hendrickson
Tree Lab Questions

1. Recursive algorithms work well for trees because recursion allows for storing areas that have been traversed on the system stack, so that all avenues can be explored. Similar to the maze example from the chapter on recursion. Recursion also works well when the same steps have to be repeated on different parts of a data structure and is often simpler and more elegant than iteration with a loop. The same way an array is continuously broken and half and searched for a binary search, traversing a tree requires breaking a large tree into smaller trees.

2. Binary trees are only efficient when they are balanced. A balanced binary tree can be searched quickly, with growth of O(log n). If the tree is unbalanced, it can become similar to a linked list, which has a search growth of O(n). Inserting elements in binary trees requires similar operations no matter what type it is, and are similar to a Doubly Linked List in efficiency. The most efficient types of binary trees are self balancing.

3. A level order traversal requires the use of some kind of collection to hold all the elements in a level, then those items are searched in order. A Queue is the best type of collection for this, since the items can be added to the queue from left to right and then dealt with in order, for each level. A recursive level order traversal is possible, but it requires visiting each node twice, which makes it much less efficient than using a while loop and a queue.