🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉
Avatar of DavidNovikov

DavidNovikov's solution

to Binary Search Tree in the C Track

Published at Sep 17 2020 · 0 comments
Instructions
Test suite
Solution

Insert and search for numbers in a binary tree.

When we need to represent sorted data, an array does not make a good data structure.

Say we have the array [1, 3, 4, 5], and we add 2 to it so it becomes [1, 3, 4, 5, 2] now we must sort the entire array again! We can improve on this by realizing that we only need to make space for the new item [1, nil, 3, 4, 5], and then adding the item in the space we added. But this still requires us to shift many elements down by one.

Binary Search Trees, however, can operate on sorted data much more efficiently.

A binary search tree consists of a series of connected nodes. Each node contains a piece of data (e.g. the number 3), a variable named left, and a variable named right. The left and right variables point at nil, or other nodes. Since these other nodes in turn have other nodes beneath them, we say that the left and right variables are pointing at subtrees. All data in the left subtree is less than or equal to the current node's data, and all data in the right subtree is greater than the current node's data.

For example, if we had a node containing the data 4, and we added the data 2, our tree would look like this:

  4
 /
2

If we then added 6, it would look like this:

  4
 / \
2   6

If we then added 3, it would look like this

   4
 /   \
2     6
 \
  3

And if we then added 1, 5, and 7, it would look like this

      4
    /   \
   /     \
  2       6
 / \     / \
1   3   5   7

Getting Started

Make sure you have read the "Guides" section of the C track on the Exercism site. This covers the basic information on setting up the development environment expected by the exercises.

Passing the Tests

Get the first test compiling, linking and passing by following the three rules of test-driven development.

The included makefile can be used to create and run the tests using the test task.

make test

Create just the functions you need to satisfy any compiler errors and get the test to fail. Then write just enough code to get the test to pass. Once you've done that, move onto the next test.

As you progress through the tests, take the time to refactor your implementation for readability and expressiveness and then go on to the next test.

Try to use standard C99 facilities in preference to writing your own low-level algorithms or facilities by hand.

Source

Josh Cheek https://twitter.com/josh_cheek

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

test_binary_search_tree.c

#include "vendor/unity.h"
#include "../src/binary_search_tree.h"
#include <stdlib.h>
#include <stdbool.h>

#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))

void setUp(void)
{
}

void tearDown(void)
{
}

static void test_data_data_is_retained(void)
{
   int tree_data[] = { 4 };
   node_t *tree = build_tree(tree_data, ARRAY_SIZE(tree_data));

   TEST_ASSERT_NOT_NULL(tree);
   TEST_ASSERT_EQUAL_INT(4, tree->data);
   TEST_ASSERT_NULL(tree->left);
   TEST_ASSERT_NULL(tree->right);

   free_tree(tree);
}

static void test_data_smaller_number_at_left_node(void)
{
   TEST_IGNORE();               // delete this line to run test
   int tree_data[] = { 4, 2 };
   node_t *tree = build_tree(tree_data, ARRAY_SIZE(tree_data));

   TEST_ASSERT_NOT_NULL(tree);
   TEST_ASSERT_EQUAL_INT(4, tree->data);
   TEST_ASSERT_NOT_NULL(tree->left);
   TEST_ASSERT_NULL(tree->right);

   TEST_ASSERT_EQUAL_INT(2, tree->left->data);
   TEST_ASSERT_NULL(tree->left->left);
   TEST_ASSERT_NULL(tree->left->right);

   free_tree(tree);
}

static void test_data_same_number_at_left_node(void)
{
   TEST_IGNORE();
   int tree_data[] = { 4, 4 };
   node_t *tree = build_tree(tree_data, ARRAY_SIZE(tree_data));

   TEST_ASSERT_NOT_NULL(tree);
   TEST_ASSERT_EQUAL_INT(4, tree->data);
   TEST_ASSERT_NOT_NULL(tree->left);
   TEST_ASSERT_NULL(tree->right);

   TEST_ASSERT_EQUAL_INT(4, tree->left->data);
   TEST_ASSERT_NULL(tree->left->left);
   TEST_ASSERT_NULL(tree->left->right);

   free_tree(tree);
}

static void test_data_greater_number_at_right_node(void)
{
   TEST_IGNORE();
   int tree_data[] = { 4, 5 };
   node_t *tree = build_tree(tree_data, ARRAY_SIZE(tree_data));

   TEST_ASSERT_NOT_NULL(tree);
   TEST_ASSERT_EQUAL_INT(4, tree->data);
   TEST_ASSERT_NULL(tree->left);
   TEST_ASSERT_NOT_NULL(tree->right);

   TEST_ASSERT_EQUAL_INT(5, tree->right->data);
   TEST_ASSERT_NULL(tree->right->left);
   TEST_ASSERT_NULL(tree->right->right);

   free_tree(tree);
}

static void test_data_can_create_complex_tree(void)
{
   TEST_IGNORE();
   int tree_data[] = { 4, 2, 6, 1, 3, 5, 7 };
   node_t *tree = build_tree(tree_data, ARRAY_SIZE(tree_data));

   TEST_ASSERT_NOT_NULL(tree);
   TEST_ASSERT_EQUAL_INT(4, tree->data);
   TEST_ASSERT_NOT_NULL(tree->left);
   TEST_ASSERT_NOT_NULL(tree->right);

   TEST_ASSERT_EQUAL_INT(2, tree->left->data);
   TEST_ASSERT_NOT_NULL(tree->left->left);
   TEST_ASSERT_NOT_NULL(tree->left->right);

   TEST_ASSERT_EQUAL_INT(6, tree->right->data);
   TEST_ASSERT_NOT_NULL(tree->right->left);
   TEST_ASSERT_NOT_NULL(tree->right->right);

   TEST_ASSERT_EQUAL_INT(1, tree->left->left->data);
   TEST_ASSERT_NULL(tree->left->left->left);
   TEST_ASSERT_NULL(tree->left->left->right);

   TEST_ASSERT_EQUAL_INT(3, tree->left->right->data);
   TEST_ASSERT_NULL(tree->left->right->left);
   TEST_ASSERT_NULL(tree->left->right->right);

   TEST_ASSERT_EQUAL_INT(5, tree->right->left->data);
   TEST_ASSERT_NULL(tree->right->left->left);
   TEST_ASSERT_NULL(tree->right->left->right);

   TEST_ASSERT_EQUAL_INT(7, tree->right->right->data);
   TEST_ASSERT_NULL(tree->right->right->left);
   TEST_ASSERT_NULL(tree->right->right->right);

   free_tree(tree);
}

static void test_sorted_data_can_sort_single_number(void)
{
   TEST_IGNORE();
   int tree_data[] = { 2 };
   node_t *tree = build_tree(tree_data, ARRAY_SIZE(tree_data));

   int expected[] = { 2 };
   int *actual = sorted_data(tree);
   TEST_ASSERT_EQUAL_INT_ARRAY(expected, actual, ARRAY_SIZE(expected));

   free_tree(tree);
   free(actual);
}

static void
test_sorted_data_can_sort_if_second_number_is_smaller_than_first(void)
{
   TEST_IGNORE();
   int tree_data[] = { 2, 1 };
   node_t *tree = build_tree(tree_data, ARRAY_SIZE(tree_data));

   int expected[] = { 1, 2 };
   int *actual = sorted_data(tree);
   TEST_ASSERT_EQUAL_INT_ARRAY(expected, actual, ARRAY_SIZE(expected));

   free_tree(tree);
   free(actual);
}

static void test_sorted_data_can_sort_if_second_number_is_same_as_first(void)
{
   TEST_IGNORE();
   int tree_data[] = { 2, 2 };
   node_t *tree = build_tree(tree_data, ARRAY_SIZE(tree_data));

   int expected[] = { 2, 2 };
   int *actual = sorted_data(tree);
   TEST_ASSERT_EQUAL_INT_ARRAY(expected, actual, ARRAY_SIZE(expected));

   free_tree(tree);
   free(actual);
}

static void
test_sorted_data_can_sort_if_second_number_is_greater_than_first(void)
{
   TEST_IGNORE();
   int tree_data[] = { 2, 3 };
   node_t *tree = build_tree(tree_data, ARRAY_SIZE(tree_data));

   int expected[] = { 2, 3 };
   int *actual = sorted_data(tree);
   TEST_ASSERT_EQUAL_INT_ARRAY(expected, actual, ARRAY_SIZE(expected));

   free_tree(tree);
   free(actual);
}

static void test_sorted_data_can_sort_complex_tree(void)
{
   TEST_IGNORE();
   int tree_data[] = { 2, 1, 3, 6, 7, 5 };
   node_t *tree = build_tree(tree_data, ARRAY_SIZE(tree_data));

   int expected[] = { 1, 2, 3, 5, 6, 7 };
   int *actual = sorted_data(tree);
   TEST_ASSERT_EQUAL_INT_ARRAY(expected, actual, ARRAY_SIZE(expected));

   free_tree(tree);
   free(actual);
}

int main(void)
{
   UnityBegin("test/test_binary_search_tree.c");

   RUN_TEST(test_data_data_is_retained);
   RUN_TEST(test_data_smaller_number_at_left_node);
   RUN_TEST(test_data_same_number_at_left_node);
   RUN_TEST(test_data_greater_number_at_right_node);
   RUN_TEST(test_data_can_create_complex_tree);
   RUN_TEST(test_sorted_data_can_sort_single_number);
   RUN_TEST(test_sorted_data_can_sort_if_second_number_is_smaller_than_first);
   RUN_TEST(test_sorted_data_can_sort_if_second_number_is_same_as_first);
   RUN_TEST(test_sorted_data_can_sort_if_second_number_is_greater_than_first);
   RUN_TEST(test_sorted_data_can_sort_complex_tree);

   return UnityEnd();
}
#include "binary_search_tree.h"
#include "stdlib.h"
static void addNodeToTree(node_t *tree, int value);
static int treeSize(node_t *tree);

node_t *build_tree(int *tree_data, size_t tree_data_len)
{
   node_t *nNode = malloc(sizeof(node_t));
   nNode->right = NULL;
   nNode->left = NULL;
   nNode->data = tree_data[0];
   for(unsigned int i = 1; i < tree_data_len; i++)
   {
      addNodeToTree(nNode, tree_data[i]);
   }
   return nNode;
}

/*
This method will count up the nodes in the tree recursively
*/
static int treeSize(node_t *tree)
{
   int size = 0;

   //first check if the tree exists, if it is the root node this is possible, add the size of the left and right subtrees
   if(tree != NULL)
   {
      size = 1 + (tree->left != NULL) * treeSize(tree->left) + (tree->right != NULL) * treeSize(tree->right);
   }

   return size;
}

/*
This method will add a node to the tree passed to it, it uses recursion to place the element
@requires *tree is not null, value is not null
*/
static void addNodeToTree(node_t *tree, int value)
{
   //if there is no data in the tree and the data to the top node
   if(tree->data == 0)
   {
      tree->data = value;
   }
   //there is data in the tree,
   //add it to left node if it is less than or equal to the root node,
   // otherwise add it to the right node
   else if(tree->data >= value)
   {
      if(tree->left == NULL)
      {
         node_t *nNode = malloc(sizeof(node_t));
         nNode->right = NULL;
         nNode->left = NULL;
         nNode->data = value;
         tree->left = nNode;
      }
      else
      {
         addNodeToTree(tree->left, value);
      }
   }
   else
   {
      if(tree->right == NULL)
      {
         node_t *nNode = malloc(sizeof(node_t));
         nNode->right = NULL;
         nNode->left = NULL;
         nNode->data = value;
         tree->right = nNode;
      }
      else
      {
         addNodeToTree(tree->right, value);
      }
   }
}

void free_tree(node_t *tree)
{
   tree->data = 0;
   tree->right = NULL;
   tree->left = NULL;
}

int *sorted_data(node_t *tree)
{
   int *arr = NULL;
   int size = treeSize(tree);

   //don't have to worry about tree being null since treeSize will catch it
   if(size)
   {
      arr = calloc(size, sizeof(int));
      unsigned int leftSize = treeSize(tree->left);
      unsigned int rightSize = treeSize(tree->right);

      //applying similar logic as above here, if a subtree is null the treeSize will catch it
      if(leftSize)
      {
         for(unsigned int i = 0; i < leftSize; i++)
         {
            arr[i] = sorted_data(tree->left)[i];
         }
      }
      arr[leftSize] = tree->data;
      if(rightSize)
      {
         for(unsigned int i = 0; i < rightSize; i++)
         {
            arr[i + leftSize + 1] = sorted_data(tree->right)[i];
         }
      }
   }

   return arr;
}

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?