Use Stack to do in order traversal

2 files changed, 43 insertions, 6 deletions

diff --git a/src/02/05/btree.c b/src/02/05/btree.c
index 23d3fbc..3fd4e31 100644
--- a/src/02/05/btree.c
+++ b/src/02/05/btree.c
@@ -31,12 +31,27 @@ void btree_pre_order_number(BTree *tree) {
   //right
 }
 
-void btree_in_order_number(BTree *tree) {
-  //use a stack
-  //
-  // left
-  // self
-  // right
+void btree_in_order_number(BTree *root) {
+  BTree *original = root;
+  if (root == NULL) return;
+
+  Stack *stack = stack_init();
+  int i = 0;
+
+  while (true) {
+    if (root) {
+      stack_push(stack, root);
+      root = root->left;
+    }
+    else {
+      if (stack_size(stack) == 0)
+        break;
+      root = stack_pop(stack);
+      original->in_order[i] = root->data;
+      ++i;
+      root = root->right;
+    }
+  }
 }
 
 void btree_post_order_number(BTree *tree) {
diff --git a/src/02/05/btree_test.c b/src/02/05/btree_test.c
index 794e09b..7c605c2 100644
--- a/src/02/05/btree_test.c
+++ b/src/02/05/btree_test.c
@@ -21,6 +21,27 @@ Ensure(BinaryTree, when_the_tree_has_a_single_node_it_returns_the_items_in_order
   assert_that(tree->in_order[0], is_equal_to(10));
 }
 
+Ensure(BinaryTree, when_the_tree_has_multiple_levels_it_returns_the_items_in_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);
+
+  btree_in_order_number(tree);
+
+  assert_that(tree->in_order[0], is_equal_to(3));
+  assert_that(tree->in_order[1], is_equal_to(5));
+  assert_that(tree->in_order[2], is_equal_to(7));
+  assert_that(tree->in_order[3], is_equal_to(10));
+  assert_that(tree->in_order[4], is_equal_to(12));
+  assert_that(tree->in_order[5], is_equal_to(15));
+  assert_that(tree->in_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) {
@@ -102,6 +123,7 @@ TestSuite *btree_tests() {
   TestSuite *suite = create_test_suite();
   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,