Cache pre order traversal of tree

2 files changed, 50 insertions, 6 deletions

diff --git a/src/02/05/btree.c b/src/02/05/btree.c
index 18821e7..be5d04a 100644
--- a/src/02/05/btree.c
+++ b/src/02/05/btree.c
@@ -22,13 +22,28 @@ BTree *btree_init(int data) {
   return tree;
 }
 
-void btree_pre_order_number(BTree *tree) {
+void btree_pre_order_number(BTree *root) {
+  BTree *original = root;
+  if (root == NULL) return;
+
   Stack *stack = stack_init();
-  /*stack_push(stack, tree);*/
-  //use a stack
-  //self
-  //left
-  //right
+  int i = 0;
+
+  stack_push(stack, root);
+  printf("[ ");
+  while (stack_size(stack) > 0) {
+    root = stack_pop(stack);
+    original->pre_order[i++] = root->data;
+    printf("%d ", root->data);
+
+    if (root->right != NULL) {
+      stack_push(stack, root->right);
+    }
+    if (root->left != NULL) {
+      stack_push(stack, root->left);
+    }
+  }
+  printf("]\n");
 }
 
 void btree_in_order_number(BTree *root) {
diff --git a/src/02/05/btree_test.c b/src/02/05/btree_test.c
index 7c605c2..5e85c33 100644
--- a/src/02/05/btree_test.c
+++ b/src/02/05/btree_test.c
@@ -42,6 +42,34 @@ Ensure(BinaryTree, when_the_tree_has_multiple_levels_it_returns_the_items_in_ord
   assert_that(tree->in_order[6], is_equal_to(18));
 }
 
+Ensure(BinaryTree, when_the_tree_has_multiple_levels_it_returns_the_items_in_pre_order) {
+  BTree *tree = btree_insert(NULL, 10);
+
+  btree_insert(tree, 5);
+  btree_insert(tree, 15);
+  btree_insert(tree, 7);
+  btree_insert(tree, 12);
+  btree_insert(tree, 18);
+  btree_insert(tree, 3);
+  /*
+      10
+    /    \
+  5      15
+ /  \    /  \
+3    7  12   18
+   */
+
+  btree_pre_order_number(tree);
+
+  assert_that(tree->pre_order[0], is_equal_to(10));
+  assert_that(tree->pre_order[1], is_equal_to(5));
+  assert_that(tree->pre_order[2], is_equal_to(3));
+  assert_that(tree->pre_order[3], is_equal_to(7));
+  assert_that(tree->pre_order[4], is_equal_to(15));
+  assert_that(tree->pre_order[5], is_equal_to(12));
+  assert_that(tree->pre_order[6], is_equal_to(18));
+}
+
 Ensure(
     BinaryTree,
     when_inserting_an_item_less_than_the_root_in_a_tree_it_creates_a_node_on_the_left_side) {
@@ -124,6 +152,7 @@ TestSuite *btree_tests() {
   add_test_with_context(suite, BinaryTree, when_the_tree_is_NULL);
   add_test_with_context(suite, BinaryTree, when_the_tree_has_a_single_node_it_returns_the_items_in_order);
   add_test_with_context(suite, BinaryTree, when_the_tree_has_multiple_levels_it_returns_the_items_in_order);
+  add_test_with_context(suite, BinaryTree, when_the_tree_has_multiple_levels_it_returns_the_items_in_pre_order);
 
   add_test_with_context(
       suite, BinaryTree,