Commit fddc2c7

@@ -2,6 +2,12 @@
 #include <stdio.h>
 #include <stdlib.h>
 
+/**
+ * Initialize a new node for a Binary Tree.
+ *
+ * @param data the data to assign to the root of the tree.
+ * @return The root of the binary tree.
+ */
 Node *initialize(int data) {
   Node *item = malloc(sizeof(Node));
   item->data = data;
@@ -10,6 +16,16 @@ Node *initialize(int data) {
   return item;
 }
 
+/*
+ * Traverses a binary tree using the traversal algorithm specified.
+ * Time: O(n)
+ * Space: O(1)
+ *
+ * @param node The root of the binary tree
+ * @param vistior A callback function to invoke on each node during the tree
+ * traversal
+ * @param traversal Specifies what type of traversal to perform
+ */
 void traverse(Node *node, Visitor visitor, enum Traversal traversal) {
   if (!node)
     return;
@@ -36,10 +52,26 @@ void traverse(Node *node, Visitor visitor, enum Traversal traversal) {
   }
 }
 
+/**
+ * Frees the memory allocated for a node in a tree
+ *
+ * @param node The node in the binary tree to free
+ */
 static void destructor(Node *node) { free(node); }
 
-void destroy(Node *head) { traverse(head, destructor, POSTORDER); }
+/**
+ * Frees the memory associated with each node in a binary tree.
+ *
+ * @param root The root of the tree
+ */
+void destroy(Node *root) { traverse(root, destructor, POSTORDER); }
 
+/**
+ * A helper method to print out a visual representation of the tree
+ *
+ * @param node A node in a binary tree.
+ * @param level The level in the tree that the node is at
+ */
 void inspect(Node *node, int level) {
   if (!node)
     return;

@@ -1,3 +1,6 @@
+/**
+ * A struct to represent a node in a Binary Tree
+ */
 struct node {
   int data;
   struct node *left;
@@ -5,8 +8,21 @@ struct node {
 };
 
 typedef struct node Node;
+
+/**
+ * A signature of a function pointer
+ * that can be used to traverse a binary tree.
+ */
 typedef void(Visitor)(Node* node);
-enum Traversal { INORDER = 1, PREORDER = 2, POSTORDER = 4 };
+
+/**
+ * The different types of traversals that the binary tree can perform
+ */
+enum Traversal {
+  INORDER = 1,   // In order traversal
+  PREORDER = 2,  // Pre order traversal
+  POSTORDER = 4  // Post order traversal
+};
 
 Node *initialize(int data);
 void traverse(Node *node, Visitor visitor, enum Traversal traversal);

@@ -2,6 +2,11 @@
 #include <limits.h>
 #include <stdio.h>
 
+/**
+ * A helper function used
+ * to print a visual representation
+ * of a Binary Tree
+ */
 static void inspect(BTree *tree, int level) {
   if (!tree)
     return;
@@ -14,6 +19,19 @@ static void inspect(BTree *tree, int level) {
   inspect(tree->right, level + 1);
 }
 
+/**
+ * A recursive function that can
+ * be used to ensure that each node in
+ * a Binary Tree satisfies the
+ * Binary Search Tree property.
+ *
+ * @param tree A tree or subtree to verify
+ * @param min the minimum value that each node must be greater than
+ * @param max the maximum value that each node must be less than.
+ * @return Returns tree when the tree is a binary search tree, otherwise false.
+ *
+ *
+ */
 static bool in_range(BTree *tree, int min, int max) {
   if (!tree)
     return true;
@@ -25,6 +43,12 @@ static bool in_range(BTree *tree, int min, int max) {
   return in_range(tree->left, min, data) && in_range(tree->right, data, max);
 }
 
+/**
+ * Initializes a binary tree.
+ *
+ * @param the data to assign to the root node in the tree.
+ * @return the root of the tree.
+ */
 BTree *btree_init(int data) {
   BTree *tree = malloc(sizeof(BTree));
   tree->left = NULL;
@@ -33,6 +57,19 @@ BTree *btree_init(int data) {
   return tree;
 }
 
+/**
+ * A function that determines if a binary tree
+ * is a binary search tree or not.
+ *
+ * @param tree The root of the tree to inspect
+ * @return Returns true when the tree is a binary search tree;
+ */
 bool btree_is_bst(BTree *tree) { return in_range(tree, INT_MIN, INT_MAX); }
 
+/**
+ * A helper function used to print a visual
+ * representation of the binary tree.
+ *
+ * @param tree The tree or subtree to inspect
+ */
 void btree_inspect(BTree *tree) { inspect(tree, 0); }

@@ -1,1 +1,3 @@
-Design a recursive linear-time algorithm that tests whether a binary tree satisfies the search tree order property at every node.
+Design a recursive linear-time algorithm that
+tests whether a binary tree satisfies the
+search tree order property at every node.

@@ -1,6 +1,13 @@
 #include "btree.h"
 #include <stdio.h>
 
+/**
+ * A helper function used to print a visual
+ * representation of a binary tree.
+ *
+ * @param tree the tree or subtree to inspect
+ * @param level the level of the subtree
+ */
 static void inspect(BTree *tree, int level) {
   if (!tree)
     return;
@@ -13,6 +20,12 @@ static void inspect(BTree *tree, int level) {
   inspect(tree->right, level + 1);
 }
 
+/**
+ * Initializes the root of a binary tree
+ *
+ * @param data the data to assign to the root of the tree.
+ * @return Returns the root of the tree.
+ */
 BTree *btree_init(int data) {
   BTree *tree = malloc(sizeof(BTree));
   tree->left = NULL;
@@ -21,25 +34,34 @@ BTree *btree_init(int data) {
   return tree;
 }
 
+/**
+ * Inserts a new node into a binary tree.
+ *
+ * @param tree the tree to insert the new new into
+ * @return Returns the root of the tree.
+ */
 BTree *btree_insert(BTree *tree, int data) {
   if (!tree)
     return btree_init(data);
 
-  if (data <= tree->data) {
-    if (tree->left) {
+  if (data <= tree->data)
+    if (tree->left)
       btree_insert(tree->left, data);
-    } else {
+    else
       tree->left = btree_init(data);
-    }
-  } else {
-    if (tree->right) {
-      btree_insert(tree->right, data);
-    } else {
-      tree->right = btree_init(data);
-    }
-  }
+  else if (tree->right)
+    btree_insert(tree->right, data);
+  else
+    tree->right = btree_init(data);
 
   return tree;
 }
 
+/**
+ * A helper function used to print
+ * a visual representation of a binary
+ * tree.
+ *
+ * @param tree The root of the tree to inspect
+ */
 void btree_inspect(BTree *tree) { inspect(tree, 0); }

@@ -1,1 +1,24 @@
-int main(int argc, char *argv[]) { return 0; }
+#include "btree.h"
+#include <stdio.h>
+
+int main(int argc, char *argv[]) {
+  printf("=== COMP-272 - Assignment 02 - Question 03 ===\n");
+  printf("Tree 1: unbalanced tree\n");
+  BTree *tree = btree_insert(NULL, 1);
+  btree_insert(tree, 5);
+  btree_insert(tree, 2);
+  btree_insert(tree, 4);
+  btree_insert(tree, 3);
+  btree_inspect(tree);
+
+  printf("Tree 2: balanced tree\n");
+  tree = btree_insert(NULL, 3);
+  btree_insert(tree, 2);
+  btree_insert(tree, 4);
+  btree_insert(tree, 1);
+  btree_insert(tree, 5);
+  btree_inspect(tree);
+
+  printf("Bye\n");
+  return 0;
+}

@@ -4,6 +4,12 @@
 #include <stdlib.h>
 #include <string.h>
 
+/**
+ * Initialize a new hash table.
+ *
+ * @param size The number of buckets to allocate for the chash table.
+ * @return Returns the hash table.
+ */
 Hash *hash_init(int size) {
   Hash *hash = malloc(sizeof(Hash));
   hash->size = size;
@@ -11,8 +17,26 @@ Hash *hash_init(int size) {
   return hash;
 }
 
-unsigned int hash_index(Hash *hash, int key) { return key % hash->size; }
+/**
+ * Computes a hash code for the given key.
+ *
+ * @param hash The hash table that the key is used in.
+ * @param key The key to produce a hash code for
+ * @return Returns a hash code for the given key.
+ */
+unsigned int hash_code(Hash *hash, int key) { return key % hash->size; }
 
+/**
+ * A function to search for a specific key in a linked list.
+ * This performs a O(n) search to find the matching key.
+ * A possible optimization would be to convert this to do a binary
+ * search for the given key using a binary search tree instead of a linked
+ * list.
+ *
+ * @param list The linked list to search for the given key
+ * @param key The key to search for in the linked list
+ * @return Returns the data associated with the given key.
+ */
 void *search(Node *list, int key) {
   Node *current = list;
 
@@ -26,14 +50,30 @@ void *search(Node *list, int key) {
   return NULL;
 }
 
+/**
+ * A function to fetch a specify value from a hash table by key.
+ *
+ * @param hash The hash table to search.
+ * @param key The key associated with the value to return
+ * @return Returns the data associated with the key or NULL if the key is not
+ * found.
+ */
 void *hash_get(Hash *hash, int key) {
-  unsigned int bucket = hash_index(hash, key);
+  unsigned int bucket = hash_code(hash, key);
   Node *n = hash->buckets + bucket;
   return (n->data) ? search(n, key) : NULL;
 }
 
+/**
+ * A function to set the value associated with a key
+ * in a hash table.
+ *
+ * @param hash The hash table to insert the key/value pair into
+ * @param key The key associated with the value to insert.
+ * @param value The value associated with the key to insert.
+ */
 void hash_set(Hash *hash, int key, void *value) {
-  unsigned int bucket = hash_index(hash, key);
+  unsigned int bucket = hash_code(hash, key);
   Tuple *tuple = tuple_initialize(key, value);
   Node *n = hash->buckets + bucket;
 
@@ -43,6 +83,11 @@ void hash_set(Hash *hash, int key, void *value) {
     hash->buckets[bucket] = *list_initialize(tuple);
 }
 
+/**
+ * A function that pretty prints a key/value pair.
+ *
+ * @param data The Tuple to print.
+ */
 void print_tuple(void *data) {
   Tuple *t = data;
 
@@ -52,6 +97,11 @@ void print_tuple(void *data) {
     printf("(nil)");
 }
 
+/**
+ * Prints a visual representation of a hash table.
+ *
+ * @param hash The hash table to inspect
+ */
 void hash_inspect(Hash *hash) {
   for (int i = 0; i < hash->size; i++) {
     printf("%2d: ", i);

@@ -2,6 +2,12 @@
 #include <stdio.h>
 #include <stdlib.h>
 
+/**
+ * Initializes a new node for a linked list.
+ *
+ * @param data The data to bind to the new node in the list.
+ * @return Returns a new linked list node
+ */
 Node *list_initialize(void *data) {
   Node *node = malloc(sizeof(Node));
   node->data = data;
@@ -9,6 +15,13 @@ Node *list_initialize(void *data) {
   return node;
 }
 
+/**
+ * Adds a new item to the tail of a linked list
+ *
+ * @param head The head of a linked list
+ * @param data The data to add to the tail of a linked list
+ * @return Returns the new node tail node
+ */
 Node *list_add(Node *head, void *data) {
   Node *tail;
   Node *tmp = head;
@@ -23,6 +36,13 @@ Node *list_add(Node *head, void *data) {
   return tail->next;
 }
 
+/**
+ * Returns a specific node by zero based index in a linked list.
+ *
+ * @param self the head of the linked list
+ * @param index the offset from the head of the node to return
+ * @return Returns the node at the specified offset or NULL.
+ */
 Node *list_get(Node *self, int index) {
   if (!self || index < 0)
     return NULL;
@@ -34,6 +54,12 @@ Node *list_get(Node *self, int index) {
   return self;
 }
 
+/**
+ * Returns the total number of nodes in a linked list.
+ *
+ * @param head The head of a linked list
+ * @returns Returns the # of items in the list.
+ */
 int list_size(Node *head) {
   int i = 0;
   for (Node *tmp = head; tmp && tmp != NULL; tmp = tmp->next)
@@ -41,6 +67,12 @@ int list_size(Node *head) {
   return i;
 }
 
+/**
+ * Prints a visual representation of a linked list.
+ *
+ * @param self The head of the linked list
+ * @param printer A callback function to invoke to print each item.
+ */
 void list_inspect(Node *self, Printer printer) {
   if (!self)
     return;

@@ -1,6 +1,13 @@
 #include "tuple.h"
 #include "stdlib.h"
 
+/**
+ * Initializes a new tuple bound to a key/value pair.
+ *
+ * @param key The key to bind to
+ * @param value The value to bind to
+ * @return Returns a new Tuple
+ */
 Tuple *tuple_initialize(int key, void *value) {
   Tuple *tuple = malloc(sizeof(Tuple));
   tuple->key = key;
@@ -8,4 +15,9 @@ Tuple *tuple_initialize(int key, void *value) {
   return tuple;
 }
 
+/**
+ * A destructor for a Tuple
+ *
+ * @param tuple The tuple to free
+ */
 void tuple_destroy(Tuple *tuple) { return free(tuple); }

@@ -2,6 +2,12 @@
 #include "stack.h"
 #include <stdio.h>
 
+/**
+ * Prints a visual representation of a binary tree
+ *
+ * @param tree The tree or subtree to print
+ * @param level The level in the tree that the subtree belongs to
+ */
 static void inspect(BTree *tree, int level) {
   if (!tree)
     return;
@@ -14,6 +20,12 @@ static void inspect(BTree *tree, int level) {
   inspect(tree->right, level + 1);
 }
 
+/**
+ * Initializes a new instance of a binary tree.
+ *
+ * @param data The data to bind to the root of the new subtree.
+ * @return Returns the new subtree.
+ */
 BTree *btree_init(int data) {
   BTree *tree = malloc(sizeof(BTree));
   tree->left = NULL;
@@ -22,26 +34,40 @@ BTree *btree_init(int data) {
   return tree;
 }
 
-void btree_pre_order_number(BTree *root) {
-  BTree *original = root;
-  if (root == NULL)
+/**
+ * Performs and caches the result of a pre order traversal
+ * on a binary tree. Cached results are stored in the root of
+ * the tree and not on each node of the tree.
+ *
+ * @param tree The subtree to perform the traversal on
+ */
+void btree_pre_order_number(BTree *tree) {
+  BTree *original = tree;
+  if (tree == NULL)
     return;
 
   Stack *stack = stack_init();
   int i = 0;
 
-  stack_push(stack, root);
+  stack_push(stack, tree);
   while (stack_size(stack) > 0) {
-    root = stack_pop(stack);
-    original->pre_order[i++] = root->data;
+    tree = stack_pop(stack);
+    original->pre_order[i++] = tree->data;
 
-    if (root->right != NULL)
-      stack_push(stack, root->right);
-    if (root->left != NULL)
-      stack_push(stack, root->left);
+    if (tree->right != NULL)
+      stack_push(stack, tree->right);
+    if (tree->left != NULL)
+      stack_push(stack, tree->left);
   }
 }
 
+/**
+ * Performs and caches the result of an in order traversal
+ * on a binary tree. Cached results are stored in the root of
+ * the tree and not on each node of the tree.
+ *
+ * @param root The subtree to perform the traversal on
+ */
 void btree_in_order_number(BTree *root) {
   BTree *original = root;
   if (root == NULL)
@@ -65,6 +91,13 @@ void btree_in_order_number(BTree *root) {
   }
 }
 
+/**
+ * Performs and caches the result of an post order traversal
+ * on a binary tree. Cached results are stored in the root of
+ * the tree and not on each node of the tree.
+ *
+ * @param root The subtree to perform the traversal on
+ */
 void btree_post_order_number(BTree *root) {
   BTree *original = root;
   if (root == NULL)
@@ -92,6 +125,13 @@ void btree_post_order_number(BTree *root) {
   }
 }
 
+/**
+ * Insert a new items into a binary tree.
+ *
+ * @param tree The tree to insert the data into.
+ * @param data The data to insert into the tree.
+ * @return Returns the new root of the tree.
+ */
 BTree *btree_insert(BTree *tree, int data) {
   if (!tree)
     return btree_init(data);
@@ -109,4 +149,9 @@ BTree *btree_insert(BTree *tree, int data) {
   return tree;
 }
 
+/**
+ * Prints a visual representation of a binary tree.
+ *
+ * @param tree The subtree to inspect.
+ */
 void btree_inspect(BTree *tree) { inspect(tree, 0); }