Complete write-up for 02/01

3 files changed, 83 insertions, 8 deletions

diff --git a/src/02/01/binary_tree.c b/src/02/01/binary_tree.c
index 16eec3d..88f4881 100644
--- a/src/02/01/binary_tree.c
+++ b/src/02/01/binary_tree.c
@@ -19,7 +19,7 @@ Node *initialize(int data) {
 /*
  * Traverses a binary tree using the traversal algorithm specified.
  * Time: O(n)
- * Space: O(1)
+ * Space: O(n) for each recursive stack frame
  *
  * @param node The root of the binary tree
  * @param vistior A callback function to invoke on each node during the tree
diff --git a/src/02/01/main.c b/src/02/01/main.c
index 81bbf2f..a55fa9c 100644
--- a/src/02/01/main.c
+++ b/src/02/01/main.c
@@ -11,6 +11,18 @@ static void visitor(Node *node) {
   visited_count++;
 }
 
+void print_traversal(Node *tree, enum Traversal direction)
+{
+  visited_count = 0;
+  memset(nodes, 0, sizeof(nodes));
+
+  traverse(tree, visitor, direction);
+
+  for (int i = 0; i < visited_count; i++)
+    printf("%d ", nodes[i]->data);
+  printf("\n");
+}
+
 int main(int argc, char *argv[]) {
   printf("=== COMP-272 - Assignment 02 - Question 01 ===\n");
 
@@ -26,15 +38,14 @@ int main(int argc, char *argv[]) {
   b->right = e;
   inspect(a, 0);
 
-  printf("\n=== Preorder traversal ===\n");
-  int visited_count = 0;
-  memset(nodes, 0, sizeof(nodes));
+  printf("\n=== Pre order traversal ===\n");
+  print_traversal(a, PREORDER);
 
-  traverse(a, visitor, PREORDER);
+  printf("\n=== In order traversal ===\n");
+  print_traversal(a, INORDER);
 
-  for (int i = 0; i < visited_count; i++) {
-    printf("%d", nodes[i]->data);
-  }
+  printf("\n=== Post order traversal ===\n");
+  print_traversal(a, POSTORDER);
 
   return 0;
 }
diff --git a/src/02/README.md b/src/02/README.md
index ae874fa..3ccc868 100644
--- a/src/02/README.md
+++ b/src/02/README.md
@@ -12,10 +12,74 @@ Design an algorithm for the following operations for a binary tree BT, and show
 * inorderNext(x): return the node visited after node x in an in-order traversal of BT.
 
 ### Description of the Code
+
+I chose to implement the binary tree traversal using
+a Visitor design pattern. The `traverse` function
+accepts a binary tree node, a callback function and
+the type of traversal to perform.
+
+The traversal uses recursion to visit each node in the
+binary tree in linear time. The space complexity is determined
+by the size of the tree because each recursive call
+adds another frame to the call stack.
+
 ### Errors and Warnings
+
+I wrote unit tests to to cover several different happy path
+scenarios and to cover the base case conditions of the
+recursive function.
+
+```bash
+モ cd 01/ && make clean && make test && ./build/test
+rm -fr build
+mkdir build
+clang    -c -o build/binary_tree.o binary_tree.c
+clang    -c -o build/binary_tree_test.o binary_tree_test.c
+clang build/binary_tree.o build/binary_tree_test.o -lcgreen -o build/test
+Running "main" (21 tests)...
+  "binary_tree_tests": 72 passes in 10ms.
+  Completed "main": 72 passes in 10ms.
+```
+
 ### Sample Input and Output
+
+The file `01/main.c` includes a small program that provides
+and example of the tree traversal. It starts by print out
+the binary tree to the console then prints the order each
+node is visited during each type of traversal.
+
+```bash
+モ cd 01/ && make clean && make && ./build/program
+rm -fr build
+mkdir build
+clang    -c -o build/binary_tree.o binary_tree.c
+clang    -c -o build/main.o main.c
+clang build/binary_tree.o build/main.o -o build/program
+=== COMP-272 - Assignment 02 - Question 01 ===
+(100)
+  (200)
+    (400)
+    (500)
+  (300)
+
+=== Pre order traversal ===
+100 200 400 500 300
+
+=== In order traversal ===
+400 200 500 100 300
+
+=== Post order traversal ===
+400 500 200 300 100
+```
+
 ### Discussion
 
+This version of the traversal requires the calling code
+to capture each node that is visited during the traversal.
+This ensures that the traversal operates in O(n) time
+but allows the calling code to cache the result of the traversal
+in a way that makes sense for it.
+
 ## Question 2
 ### Problem Statement