What is a tree?

- A tree is a set of nodes connected by edges that indicate the relationships
  among the nodes.  
- A tree is a special form of a graph.
- The nodes are arranged in levels that indicate the nodes hierarchy.
- At the top level of a tree is a single node called the root.
- The nodes of each successive level are the children of the nodes at the 
  previous level
- A node that has children is the parent of those children.
- Children that have the same parent are called siblings.
- Children are the descendants of all nodes above them in the hierarchy.
- Parents are ancestors of all nodes lower than them in the hierarchy that
  have a path from the parent to the descendant node.
- A node with no children is called a leaf node
- A node with children is an interior, or nonleaf node.
- The height of a tree is the number of levels in the tree.
- A path is a set of edges that connects two nodes in the tree in a 
  strictly descending (or ascending) hierarchical order.
- the length of the path is the number of edges that copose it.


Trees are recursive in nature; that is to say, each node of a tree is itself
a tree.  This includes the idea of the empty tree.

How many children can a node have?  We are used to dealing with binary trees,
but a general tree can have any number of children.  A tree with no more than
n children per node is called an n-ary tree.  Thus, the binary tree has
no more than 2 children per node.

For a strict n-ary tree, there are two more conditions of interest to us, 
which are fullness and completeness.  To say that a tree is full, is to say 
that each non-leaf node in the n-ary tree has exactly n children.  To say 
that a tree is complete is to say that it is full to its next to last level, 
and that the last level is filled in from left to right.

How many nodes are in a tree?
- a full or complete tree can calculate the number of nodes with the 
  formula n^h-1, where n is the number of children per node, and h is the
  height of the tree.
- this can also be expressed as the sum from i=0 to h-1 of n^i

You can reverse the calculation to calculate the height of a tree with x 
nodes, which is logn(x+1)


So, now we know what all the parts of a tree are called.  What use is it?  
in order to do anything with the tree, we have to be able to access the nodes
in the tree.  For bags, and stacks, and sets, and lists, this was a straight-
forward process, you just move linearly through the structure.  However,
our structure now has an extra dimension.  How do we move through this to
visit all the nodes?

A method of walking through the nodes of a tree is called a traversal.

There are two basic categories of tree traversal, breadth first, and depth
first.

In breadth first, we treat the levels of the tree like linear structures, and 
walk through each level in order.  The primary breadth first search is called 
a row order traversal.

In depth first, we walk through the tree in varying order dependent on the 
subtrees.  There are three main depth first traversals, preorder, inorder, 
and postorder.

preorder visits the root, then the left, then the right.
inorder visits the left, then the root, then the right.
postorder visits the left, then the right, then the root.

Note that inorder does not map to a general tree, but only makes sense for
binary trees.

examples : expression trees, decision trees, game trees