TREE
-------------------------------

 TreeNode -- has 2 pointers: left and right

 Tree Traversals

 
 traversal() algorithm:
 (in-order traversal)
 --> go left
 --> visit the node
 --> go right

  Apply the above at each
  node in the tree


 A --> go left
   B --> go left
     D --> go left
     D --> visit (42)
     D --> go right
   B --> visit (78)
   B --> go right
 A --> visit (100)
 A --> go right
   C --> go left
     E --> go left
     E --> visit (102)
     E --> go right
   C --> visit (125)
   C --> go right
     F --> go left
     F --> visit (180)
     F --> go right

 in-order:
   42 78 100 102 125 180

 traversal() algorithm:
 (pre-order traversal)
 --> visit the node
 --> go left
 --> go right


 A --> visit (100)
 A --> go left
   B --> visit (78)
   B --> go left
    etc.

 pre-order:
   100 78 42 125 102 180



 traversal() algorithm:
 (post-order traversal)
 --> go left
 --> go right
 --> visit the node

 post-order traversal:
 A --> go left
   B --> go left
     D --> go left
     D --> go right
     D --> visit (42)
   B --> go right
   B --> visit (78)
 A --> go right
   C --> go left
     E --> go left
     E --> go right
     E --> visit (102)
   C --> go right
     F --> go left
     F --> go right
     F --> visit (180)
   C --> visit (125)
 A --> visit (100)


 // Write a recursive function
 //  to count the number of
 //  odd numbers in the given
 //  tree
 //
 // No static or global variables
 int
 odd_numbers_in_tree( TreeNode<int> * root )
 {
   if ( root == NULL )
   {
     return 0;
   }
   else
   {
     // VISIT
     int count = 0;
     if ( root->value % 2 == 1 ) {  // ODD
       count = 1;
     }

     return count +
        odd_numbers_in_tree( root->left ) +
        odd_numbers_in_tree( root->right );
    }
 }


 int n = odd_numbers_in_tree( t );

 return 0 + odd( A.left ) + odd( A.right )
 return 0 + 0 + odd( B.left ) + odd( B.right ) + odd( A.right )
 return 0 + 0 + 0 + odd( D.left ) + odd( D.right ) +  etc........
 return 0 + 0 + 0 + 0 + 0 + 0 + 1 + 0 + 0 + 0 + etc.


 The use of recursion applies to tree
  data structures; also applies to other
  data structures

 merge-sort()
 -- given a vector of size N
 ----> divide N into two sub-vectors,
          each of size N/2
 ----> then call merge-sort() for each
          of those sub-lists

 the "stop" case is merge()




===========================================

 Given some set of keys that map to values

 "Hash" the key to a
   unique index in a vector

 Use a hash() function to generate the index

  vector:
 -----------
0|    0    |
 -----------
1|    0    |
 -----------
2|    0    |
 -----------   ---------------   --------- 
3|    -------->| Goldschmidt ----> Jones |
 -----------   ---------------   ---------
   etc.
 -----------   -----------
9|    -------->| Smith 0 |
 -----------   -----------


  given some key k, generate i = f(k), then
    store key k and its associated value v
    in the vector at index i

  e.g. key is a string -- take the ASCII
       value of each character and add them
       up, then use % to fit into the vector

  f(k) = hash(s) % 10;  // ==> 0-9

  "Goldschmidt" ==> 803 % 10 = 3
  "Smith" ==> 409 % 10 = 9
  "mitSh" ==> 409 % 10 = 9
  "Jones" ==> 403 % 10 = 3

  "Goldschmidt" ==> 803 % 30 = 23





  If I had 1000 names, linear search would
    take 1000 comparison operations (worst)

  If I had 1000 names, hashed into 10 index
    locations within a vector/array, take
    1 hash function and 100 comparison
    operations (worst)



  Choose a hash table of a size that's a
    prime number

  Choose a hash function that's O(1)
    and has a random uniform distribution