ðŸŽ‰ Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io ðŸŽ‰

# mbraniff's solution

## to Binary Search Tree in the C Track

Published at Jun 30 2020 · 1 comment
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.

## 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>
#include <stdio.h>

#define next_data *(tree_data++)

node_t *new_node(int data)
{
node_t *new = (node_t *)calloc(1, sizeof(node_t));
new->data = data;
new->left = NULL;
new->right = NULL;
return new;
}

node_t *build_tree(int *tree_data, size_t tree_data_len)
{
if(tree_data_len <= 0){
return NULL;
}
tree_data_len--;
while(tree_data_len--)
{
node_t *temp = new_node(next_data);
while(1)
{
if(temp->data > curr->data)
{
if(curr->right)
curr = curr->right;
else
{
curr->right = temp;
break;
}
}
else
{
if(curr->left)
curr = curr->left;
else
{
curr->left = temp;
break;
}
}
}
}

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

int* _sorted_data(node_t *tree, int* list)
{
if(tree == NULL)
{
return list;
}
list = _sorted_data(tree->left, list);
*(list++) = tree->data;
_sorted_data(tree->right, list);

return list;
}

int *sorted_data(node_t *tree)
{
int* list = calloc(100, sizeof(int));
_sorted_data(tree, list);
return list;
}``````

I did this so long ago that the exercise did not include the free.

not a fan of the trickery/macro called "next_data" - why not just pass the pointer to the new_node routine and increment in there?

On build routine I used more helper functions --but it looks like it works. Just wondering if everything in the while(1) should really be in a helper function.

### 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?
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://exercism.io/tracks/c/exercises/binary-search-tree/solutions/0fb00de838024948b173dddc4a6bb3a4", "fetch_time": 1624268063000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2021-25/segments/1623488269939.53/warc/CC-MAIN-20210621085922-20210621115922-00339.warc.gz", "warc_record_offset": 233836063, "warc_record_length": 8441, "token_count": 2565, "char_count": 9958, "score": 3.921875, "int_score": 4, "crawl": "CC-MAIN-2021-25", "snapshot_type": "latest", "language": "en", "language_score": 0.9132409691810608, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00008-of-00064.parquet"}