Commit 47400bd

@@ -0,0 +1,9 @@
+# Scheduling & Binary Search Trees
+
+* Airport with a single runway.
+* Reservations for future landings.
+* Reserve request specifies landing time t
+* Add `t` to the set `R` of landing times if no other landings are scheduled within `k` minutes.
+* Remove from set `R` after plane lands.
+* `|R| = n`
+* `O(lg n)` time where `n` is the size of the set.

@@ -1,5 +1,31 @@
+#include <stdio.h>
 #include "btree.h"
-#include "queue.h"
+#include <limits.h>
+
+static void inspect(BTree *tree, int level) {
+  if (!tree)
+    return;
+
+  BTree *current = tree;
+
+  for (int i = 0; i < level; i++)
+    printf("  ");
+  printf("%2d\n", tree->data);
+  inspect(tree->left, level + 1);
+  inspect(tree->right, level + 1);
+}
+
+static bool btree_in_range(BTree *tree, int min, int max) {
+  if (!tree)
+    return true;
+
+  int data = tree->data;
+  if (data < min || data > max)
+    return false;
+
+  return btree_in_range(tree->left, min, data) &&
+    btree_in_range(tree->right, data, max);
+}
 
 BTree *btree_init(int data) {
   BTree *tree = malloc(sizeof(BTree));
@@ -10,28 +36,5 @@ BTree *btree_init(int data) {
 }
 
 bool btree_is_bst(BTree *tree) {
-  if (!tree) {
-    return false;
-  }
-
-  Queue *queue = queue_init();
-  queue_enq(queue, tree->left);
-  queue_enq(queue, tree);
-  queue_enq(queue, tree->right);
-
-  // in order traversal
-  // fill queue
-  // iterate through queue and
-  // check if last is less than next
-  while (queue_size(queue) > 0) {
-    BTree *item = queue_deq(queue);
-    if (!item)
-      continue;
-
-    queue_enq(queue, item->left);
-    queue_enq(queue, item);
-    queue_enq(queue, item->right);
-  }
-
-  return false;
+  return btree_in_range(tree, INT_MIN, INT_MAX);
 }

@@ -7,16 +7,13 @@ BeforeEach(BinaryTree) {}
 AfterEach(BinaryTree) {}
 
 Ensure(BinaryTree, when_a_tree_is_NULL) {
-  bool result = btree_is_bst(NULL);
-
-  assert_that(result, is_equal_to(false));
+  assert_that(btree_is_bst(NULL), is_equal_to(true));
 }
 
 Ensure(BinaryTree, when_a_tree_has_a_single_node) {
   BTree *tree = btree_init(100);
-  bool result = btree_is_bst(tree);
 
-  assert_that(result, is_equal_to(true));
+  assert_that(btree_is_bst(tree), is_equal_to(true));
 }
 
 Ensure(BinaryTree, when_the_node_on_the_left_is_greater_than_the_root) {
@@ -26,12 +23,52 @@ Ensure(BinaryTree, when_the_node_on_the_left_is_greater_than_the_root) {
   assert_that(btree_is_bst(tree), is_equal_to(false));
 }
 
+Ensure(BinaryTree, when_the_node_on_the_right_is_less_than_the_root) {
+  BTree *tree = btree_init(200);
+  tree->right = btree_init(100);
+
+  assert_that(btree_is_bst(tree), is_equal_to(false));
+}
+
+Ensure(BinaryTree, when_a_node_on_the_left_subtree_is_less_than_an_ancestor) {
+  BTree *tree = btree_init(300);
+  tree->left = btree_init(100);
+  tree->left->right = btree_init(400);
+
+  assert_that(btree_is_bst(tree), is_equal_to(false));
+}
+
+Ensure(BinaryTree, when_a_node_on_the_right_subtree_is_greater_than_an_ancestor) {
+  BTree *tree = btree_init(300);
+  tree->right = btree_init(500);
+  tree->right->left = btree_init(200);
+
+  assert_that(btree_is_bst(tree), is_equal_to(false));
+}
+
+Ensure(BinaryTree, when_the_tree_is_a_binary_search_tree) {
+  BTree *tree = btree_init(10);
+  tree->left = btree_init(-5);
+  tree->left->left = btree_init(-10);
+  tree->left->right = btree_init(5);
+
+  tree->right = btree_init(25);
+  tree->right->left = btree_init(23);
+  tree->right->right = btree_init(36);
+
+  assert_that(btree_is_bst(tree), is_equal_to(true));
+}
+
 TestSuite *binary_search_tree_tests() {
   TestSuite *suite = create_test_suite();
 
   add_test_with_context(suite, BinaryTree, when_a_tree_is_NULL);
   add_test_with_context(suite, BinaryTree, when_a_tree_has_a_single_node);
   add_test_with_context(suite, BinaryTree, when_the_node_on_the_left_is_greater_than_the_root);
+  add_test_with_context(suite, BinaryTree, when_the_node_on_the_right_is_less_than_the_root);
+  add_test_with_context(suite, BinaryTree, when_a_node_on_the_left_subtree_is_less_than_an_ancestor);
+  add_test_with_context(suite, BinaryTree, when_a_node_on_the_right_subtree_is_greater_than_an_ancestor);
+  add_test_with_context(suite, BinaryTree, when_the_tree_is_a_binary_search_tree);
 
   return suite;
 }

@@ -5,7 +5,7 @@ CC=clang
 TEST_LIBS = -lcgreen
 
 BUILDDIR := build
-OBJS := $(addprefix $(BUILDDIR)/,btree.o queue.o)
+OBJS := $(addprefix $(BUILDDIR)/,btree.o)
 TEST_OBJS := $(addprefix $(BUILDDIR)/,btree_test.o)
 
 $(BUILDDIR)/%.o : %.c

@@ -1,17 +0,0 @@
-#include "queue.h"
-#include <stdlib.h>
-
-Queue *queue_init() {
-  return NULL;
-}
-
-int queue_size(Queue *queue) {
-  return 0;
-}
-
-void queue_enq(Queue *queue, void* data) {
-}
-
-void *queue_deq(Queue *queue) {
-  return NULL;
-}

@@ -1,9 +0,0 @@
-typedef struct sll_node {
-  struct sll_node *next;
-  void *data;
-} Queue;
-
-Queue *queue_init();
-int queue_size(Queue *queue);
-void *queue_deq(Queue *queue);
-void queue_enq(Queue *queue, void* data);