Perform a recursive insert into a btree

3 files changed, 61 insertions, 2 deletions

diff --git a/src/02/03/btree.c b/src/02/03/btree.c
index c5b1ed8..551c025 100644
--- a/src/02/03/btree.c
+++ b/src/02/03/btree.c
@@ -1,4 +1,17 @@
 #include "btree.h"
+#include <stdio.h>
+
+static void inspect(BTree *tree, int level) {
+  if (!tree)
+    return;
+
+  for (int i = 0; i < level; i++)
+    printf("  ");
+
+  printf("%2d\n", tree->data);
+  inspect(tree->left, level + 1);
+  inspect(tree->right, level + 1);
+}
 
 BTree *btree_init(int data) {
   BTree *tree = malloc(sizeof(BTree));
@@ -13,10 +26,22 @@ BTree *btree_insert(BTree *tree, int data) {
     return btree_init(data);
 
   if (data <= tree->data) {
-    tree->left = btree_init(data);
+    if (tree->left) {
+      btree_insert(tree->left, data);
+    } else {
+      tree->left = btree_init(data);
+    }
   } else {
-    tree->right = btree_init(data);
+    if (tree->right) {
+      btree_insert(tree->right, data);
+    } else {
+      tree->right = btree_init(data);
+    }
   }
 
   return tree;
 }
+
+void btree_inspect(BTree *tree) {
+  inspect(tree, 0);
+}
diff --git a/src/02/03/btree.h b/src/02/03/btree.h
index 6a1302c..c18fa3b 100644
--- a/src/02/03/btree.h
+++ b/src/02/03/btree.h
@@ -9,3 +9,4 @@ typedef struct btree_node {
 
 BTree *btree_init(int data);
 BTree *btree_insert(BTree *root, int data);
+void btree_inspect(BTree *tree);
diff --git a/src/02/03/btree_test.c b/src/02/03/btree_test.c
index 84720f5..49dd9e6 100644
--- a/src/02/03/btree_test.c
+++ b/src/02/03/btree_test.c
@@ -39,6 +39,37 @@ Ensure(BinaryTree, when_inserting_an_item_equal_to_the_root_in_a_tree_it_creates
   assert_that(tree->left->data, is_equal_to(10));
 }
 
+Ensure(BinaryTree, when_inserting_multiple_items_into_a_tree_it_inserts_in_the_correct_position) {
+  BTree *tree = btree_insert(NULL, 10);
+
+  btree_insert(tree, -5);
+  btree_insert(tree, 16);
+
+  assert_that(tree->data, is_equal_to(10));
+  assert_that(tree->left->data, is_equal_to(-5));
+  assert_that(tree->right->data, is_equal_to(16));
+
+  btree_insert(tree, -8);
+
+  assert_that(tree->left->left, is_not_equal_to(NULL));
+  assert_that(tree->left->left->data, is_equal_to(-8));
+
+  btree_insert(tree, 7);
+
+  assert_that(tree->left->right, is_not_equal_to(NULL));
+  assert_that(tree->left->right->data, is_equal_to(7));
+
+  btree_insert(tree, 18);
+
+  assert_that(tree->right->right, is_not_equal_to(NULL));
+  assert_that(tree->right->right->data, is_equal_to(18));
+
+  btree_insert(tree, 6);
+
+  assert_that(tree->left->right->left, is_not_equal_to(NULL));
+  assert_that(tree->left->right->left->data, is_equal_to(6));
+}
+
 TestSuite *binary_search_tree_tests() {
   TestSuite *suite = create_test_suite();
 
@@ -46,6 +77,8 @@ TestSuite *binary_search_tree_tests() {
   add_test_with_context(suite, BinaryTree, when_inserting_an_item_less_than_the_root_in_a_tree_it_creates_a_node_on_the_left_side);
   add_test_with_context(suite, BinaryTree, when_inserting_an_item_greater_than_the_root_in_a_tree_it_creates_a_node_on_the_right_side);
   add_test_with_context(suite, BinaryTree, when_inserting_an_item_equal_to_the_root_in_a_tree_it_creates_a_node_on_the_left_side);
+  add_test_with_context(suite, BinaryTree, when_inserting_multiple_items_into_a_tree_it_inserts_in_the_correct_position);
+
   return suite;
 }