Commit 8b865ca

@@ -3,13 +3,11 @@
 #include <stdlib.h>
 
 void investigate(BTree *tree) {
-  printf("Tree\n");
-  printf("---------\n");
   btree_inspect(tree);
-  printf("Is a BST? %c\n\n", btree_is_bst(tree) ? 'y' : 'n');
+  printf("Is a binary search tree? %c\n\n", btree_is_bst(tree) ? 'y' : 'n');
 }
 
-BTree *build_bst() {
+BTree *build_binary_search_tree() {
   BTree *tree = btree_init(10);
   tree->left = btree_init(-5);
   tree->left->left = btree_init(-10);
@@ -21,7 +19,7 @@ BTree *build_bst() {
   return tree;
 }
 
-BTree *build_tree() {
+BTree *build_binary_tree() {
   BTree *tree = btree_init(10);
   tree->left = btree_init(0);
   tree->left->left = btree_init(-1);
@@ -37,8 +35,13 @@ BTree *build_tree() {
 int main(int argc, char *argv[]) {
   printf("=== COMP-272 - Assignment 02 - Question 02 ===\n");
 
-  investigate(build_bst());
-  investigate(build_tree());
+  printf("Binary Search Tree\n");
+  printf("---------\n");
+  investigate(build_binary_search_tree());
+
+  printf("Binary Tree\n");
+  printf("---------\n");
+  investigate(build_binary_tree());
 
   printf("Bye\n");
   return 0;

@@ -88,10 +88,105 @@ tests whether a binary tree satisfies the
 search tree order property at every node.
 
 ### Description of the Code
+
+To determine if a binary tree satisfies the binary
+search tree order property I needed to check each
+node in the binary tree to make sure that the item
+in the left side of the node is less than the node itself
+and that the item in the right side of the node is
+greater than itself. Each descendant node must also be
+greater or less than each ancestor node depending on which side
+of the tree that node is relative to the ancestor.
+
+To perform this check I kept track of the minimum
+and maximum values that any node can be while traversing
+down the tree.
+
+For example, when traversing down a left sub tree each
+node in the left sub tree must be between the minimum
+value and the current node. When traversing down the
+right subtree each node must be between the value in
+the current node and the maximum value.
+
+To kick start the recursive call I specified an arbitrary
+min and max values that matched the boundary of the size of
+the integer. So a range (2^32/2 * -1) and (2^32/2 - 1) was used.
+
+The base case for the recursive call is when the subtree
+that is visited is a NULL.
+
 ### Errors and Warnings
+
+I wrote unit tests to test the happy day scenarios, the base
+case and a couple of edge cases.
+
+```bash
+モ make clean && make test && ./build/test
+rm -fr build
+mkdir build
+clang    -c -o build/btree.o btree.c
+clang    -c -o build/btree_test.o btree_test.c
+clang build/btree.o build/btree_test.o -lcgreen -o build/test
+Running "main" (7 tests)...
+  "binary_search_tree_tests": 7 passes in 3ms.
+  Completed "main": 7 passes in 4ms.
+```
+
+A full list of tests cases can be found in `02/*_test.c`.
+
 ### Sample Input and Output
+
+To make it easier to see that the checks are working as
+expected, I included a program in `02/main.c` that will
+build a binary search tree and a regular binary tree and
+check to see if either matches the properties of a binary
+search tree.
+
+Sample output can be seen below:
+
+```bash
+モ cd 02/ && make clean && make && ./build/program
+rm -fr build
+mkdir build
+clang    -c -o build/btree.o btree.c
+clang    -c -o build/main.o main.c
+clang build/btree.o build/main.o -o build/program
+=== COMP-272 - Assignment 02 - Question 02 ===
+Binary Search Tree
+---------
+10
+  -5
+    -10
+     5
+  25
+    23
+    36
+Is a binary search tree? y
+
+Binary Tree
+---------
+10
+   0
+    -1
+    21
+  25
+    16
+    32
+Is a binary search tree? n
+
+Bye
+```
+
 ### Discussion
 
+The recursive version of the check operates in
+`O(n)` time and `O(n)` space. The space is due
+to the allocation of a stack frame for each
+recursive call in the call stack. An iterative
+version of this same algorithm would also
+operate in linear time but could benefit
+from `O(1)` space by using pointers.
+
 ## Question 3
 ### Problem Statement