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

johnietre's solution

to Binary Search Tree in the C Track

Published at Dec 29 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();
}

src/binary_search_tree.c

#include "binary_search_tree.h"

int count(node_t *tree) {
  int c = 1;
  if (tree->left != NULL)
    c += count(tree->left);
  if (tree->right != NULL)
    c += count(tree->right);
  return c;
}

void place_node(node_t *node, int data) {
  if (node->data < data) {
    if (node->right != NULL)
      place_node(node->right, data);
    else {
      node->right = malloc(sizeof(node_t));
      node->right->data = data, node->right->right = NULL,
      node->right->left = NULL;
    }
  } else {
    if (node->left != NULL)
      place_node(node->left, data);
    else {
      node->left = malloc(sizeof(node_t));
      node->left->data = data, node->left->right = NULL,
      node->left->left = NULL;
    }
  }
}

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

int *sorted_data(node_t *tree) {
  int *rdata = NULL, *ldata = NULL, rlen = 0, llen = 0;
  if (tree->right != NULL) {
    rdata = sorted_data(tree->right);
    rlen = count(tree->right);
  }
  if (tree->left != NULL) {
    ldata = sorted_data(tree->left);
    llen = count(tree->left);
  }
  int len = count(tree);
  int *data = malloc(sizeof(int) * len);
  for (int i = 0; i < llen; i++)
    data[i] = ldata[i];
  data[llen] = tree->data;
  for (int i = 0; i < rlen; i++)
    data[i + llen + 1] = rdata[i];
  free(rdata);
  free(ldata);
  return data;
}

void free_tree(node_t *tree) {
  if (tree->right != NULL)
    free_tree(tree->right);
  if (tree->left != NULL)
    free_tree(tree->left);
  free(tree);
  tree = NULL;
}

src/binary_search_tree.h

#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H
#include <stddef.h>
#include <stdlib.h>

typedef struct node node_t;

struct node {
  node_t *right;
  node_t *left;
  int data;
};

int count(node_t *tree);
void place_node(node_t *node, int data);
node_t *build_tree(int *tree_data, size_t tree_data_len);
int *sorted_data(node_t *tree);
void free_tree(node_t *tree);

#endif

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?