Use stack to do post order traversal

2 files changed, 52 insertions, 7 deletions

diff --git a/src/02/05/btree.c b/src/02/05/btree.c
index be5d04a..0fedabd 100644
--- a/src/02/05/btree.c
+++ b/src/02/05/btree.c
@@ -30,11 +30,9 @@ void btree_pre_order_number(BTree *root) {
   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);
@@ -43,7 +41,6 @@ void btree_pre_order_number(BTree *root) {
       stack_push(stack, root->left);
     }
   }
-  printf("]\n");
 }
 
 void btree_in_order_number(BTree *root) {
@@ -69,10 +66,29 @@ void btree_in_order_number(BTree *root) {
   }
 }
 
-void btree_post_order_number(BTree *tree) {
-  // left
-  // right
-  // self
+void btree_post_order_number(BTree *root) {
+  BTree *original = root;
+  if (root == NULL)
+    return;
+
+  Stack *s1 = stack_init();
+  Stack *s2 = stack_init();
+
+  stack_push(s1, root);
+
+  while (stack_size(s1) > 0) {
+    root = stack_pop(s1);
+    stack_push(s2, root);
+
+    if (root->left) stack_push(s1, root->left);
+    if (root->right) stack_push(s1, root->right);
+  }
+
+  int i = 0;
+  while (stack_size(s2) > 0) {
+    root = stack_pop(s2);
+    original->post_order[i++] = root->data;
+  }
 }
 
 BTree *btree_insert(BTree *tree, int data) {
diff --git a/src/02/05/btree_test.c b/src/02/05/btree_test.c
index 5e85c33..ac49b46 100644
--- a/src/02/05/btree_test.c
+++ b/src/02/05/btree_test.c
@@ -70,6 +70,34 @@ Ensure(BinaryTree, when_the_tree_has_multiple_levels_it_returns_the_items_in_pre
   assert_that(tree->pre_order[6], is_equal_to(18));
 }
 
+Ensure(BinaryTree, when_the_tree_has_multiple_levels_it_returns_the_items_in_post_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_post_order_number(tree);
+
+  assert_that(tree->post_order[0], is_equal_to(3));
+  assert_that(tree->post_order[1], is_equal_to(7));
+  assert_that(tree->post_order[2], is_equal_to(5));
+  assert_that(tree->post_order[3], is_equal_to(12));
+  assert_that(tree->post_order[4], is_equal_to(18));
+  assert_that(tree->post_order[5], is_equal_to(15));
+  assert_that(tree->post_order[6], is_equal_to(10));
+}
+
 Ensure(
     BinaryTree,
     when_inserting_an_item_less_than_the_root_in_a_tree_it_creates_a_node_on_the_left_side) {
@@ -153,6 +181,7 @@ TestSuite *btree_tests() {
   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, when_the_tree_has_multiple_levels_it_returns_the_items_in_post_order);
 
   add_test_with_context(
       suite, BinaryTree,