1. ## Tree sort help

Hi Guys,

I have a problem for school and I am not able to solve it.

"You have been provided with a header file Tree.h containing only the function prototypes needed for a binary tree sorting algorithm. Create a class Tree.c that includes the header file and implements the function calls. You are to retain the same signatures and do not add any other functions. Each function prototype has comments as documentation. You can create an integer array with fixed values for testing purposes. To sort the array, you should only call bstSort. "

the Tree.h file is something like this:
Code:
```#ifndef_TREE_H_
#define_TREE_H_
/*
A binary tree node structure for integer values. Every node
has a pointer to the left child node and right child node.
If the value to be added is smaller than the value of the
current node then it is placed in the left node, otherwise
it goes in the right node. The first node of the tree
is called the root node. Nodes with no children are leaf nodes.
*/
struct Node {
int val;
struct Node *left, *right;
};

/*
Sorts an array of integers using a binary tree.
*arr is a pointer to an integer array.
n is the number of integers in the array.
*/
void bstSort(int *arr, int n);

/*
Adds an integer value to a tree node.
If n is null then it is created and assigned to the value.
If the value is smaller than the node value then it is inserted
to the left node of the current node. Otherwise it is inserted
to the right node of the current node.
*/
struct Node *insert(struct Node *n, int val);

/*
Does an inorder traversal of the tree structure and
fills in the array with the sorted values.
Pos is a reference to the current position.
*/
void storeSorted(struct Node *n, int *arr, int *pos);

/*
Destroys the binary tree structure by doing an inorder traversal
and frees the dynamically allocated memory of each node.
*/
void bstDestroy(struct Node *n);

#endif```

I tried to do it by myself following some tutorial but all of them are different from the structure I have to follow and I am losing my mind for the past few days

Could any of you help me with this?
Thank you very much.

2. Instead of following a tutorial, why not follow the instructions that your teacher helpfully provided in the comments? The key is to think of how to use insert, storeSorted, and bstDestroy to implement bstSort.

3. Hi laser, the problem is that I do not completely understand how this works and I tried to follow the tutorials to try and understand what should I do but the problem is that everything is different than the implementation, therefore I am getting lost.

Any help would be appreciated.

4. The idea is that if you keep inserting values into the binary tree such that "If the value is smaller than the node value then it is inserted to the left node of the current node. Otherwise it is inserted to the right node of the current node", then if you do "an inorder traversal of the tree structure and fills in the array with the sorted values", you would have sorted the array with the help of the binary tree.

5. Originally Posted by laserlight
The idea is that if you keep inserting values into the binary tree such that "If the value is smaller than the node value then it is inserted to the left node of the current node. Otherwise it is inserted to the right node of the current node", then if you do "an inorder traversal of the tree structure and fills in the array with the sorted values", you would have sorted the array with the help of the binary tree.
I am almost there.

I wrote the below code but it gives me some errors while running, I just need to double check it and then understand how to destroy the nodes using the bstDestroy

Code:
```#include <stdio.h>
int main()
{
int arr[] = {10, 5, 8, 20, 16, 70, 50, 9};
int n = sizeof(arr)/sizeof(arr[0]);

bstSort(arr, n);
}

struct Node {
int val;
struct Node *left, *right;
};

void bstSort(int *arr, int n)
{
struct Node *root = NULL;

root = insert(root, arr[0]);
for (int i=1; i<n; i++)
insert(root, arr[i]);

int i = 0;
storeSorted(root, arr, i);

}

struct Node * insert(struct Node *n, int val)
{
if (val < n->val)
n->left  = insert(n->left, val);
else if (val > n->val)
n->right = insert(n->right, val);

return n;
}

void storeSorted(struct Node *n, int *arr, int *pos)
{

if (n != NULL)
{
storeSorted(n->left, arr, *pos);
arr[*pos] = n->val;
storeSorted(n->right, arr, *pos);
}

}```

6. Originally Posted by masterxfile
I am almost there.

I wrote the below code but it gives me some errors while running, I just need to double check it and then understand how to destroy the nodes using the bstDestroy
Code:
```/*

Destroys the binary tree structure by doing an inorder traversal

and frees the dynamically allocated memory of each node.
*/
void bstDestroy(struct Node *n);```
Inorder traversals work in the following order (left, root, right).

Here's a general idea of how the algorithm works:
1. Traverse the left subtree, i.e., call Inorder(left-subtree)
2. Visit the root
3. Traverse the right subtree, i.e., call Inorder(right-subtree)

Hope this helps.

Also, I think your insert function is incorrect. The right and left insertions are correct but your instructions state:

If n is null then it is created and assigned to the value.
If I'm not mistaken, you'll have to check if the node is null and then perform a normal binary tree insertion. (Correct me if I'm wrong)

7. Thank you snoopfrogg,

You were right I had to create a new node.

Code:
```#include <stdio.h>#include <stdlib.h>
struct Node {
int val;
struct Node *left, *right;
};

void bstSort(int *arr, int n);
struct Node *insert(struct Node *n, int val);
void storeSorted(struct Node *n, int *arr, int *pos);
void bstDestroy(struct Node *n);

int main()
{
int arr[] = { 10, 5, 8, 20, 16, 70, 50, 9 };
int n = sizeof(arr) / sizeof(arr[0]);

bstSort(&arr, n);

for (int ii = 0; ii < n; ii++)
printf("%d\n", arr[ii]);

getchar();
return 0;
}

void bstSort(int *arr, int n)
{
struct Node *root = NULL;

// root = insert(root, arr[0]);

for (int i = 0; i < n; i++)
insert(root, arr[i]);

storeSorted(root, arr, &arr[0]);
bstDestroy(root);
}

struct Node *insert(struct Node *n, int val)
{
if (n == NULL) {
n = malloc(sizeof(struct Node));
(n)->left = NULL;
(n)->val = val;
(n)->right = NULL;
} else {
if (val < n->val)
n->left = insert(n->left, val);
else if (val > n->val)
n->right = insert(n->right, val);
}

return n;
}

void storeSorted(struct Node *n, int *arr, int *pos)
{
if (n != NULL) {
storeSorted(n->left, arr, pos);
arr[*pos] = n->val;
storeSorted(n->right, arr, pos);

}
}

void bstDestroy(struct Node *n)
{
if (n == NULL)
return;
if (n->left != NULL)
bstDestroy(n->left);
if (n->right != NULL)
bstDestroy(n->right);
free(n);
return;
}```
Now I have only one problem left.
The code above works and it creates the tree structure as needed, the only thing is that in the storeSorted function the array is sorted but it remains there.

When I go back to the top of the code it is not sorted so I might need to do some more research.

8. Originally Posted by masterxfile
Thank you snoopfrogg,

You were right I had to create a new node.

Code:
```#include <stdio.h>#include <stdlib.h>
struct Node {
int val;
struct Node *left, *right;
};

void bstSort(int *arr, int n);
struct Node *insert(struct Node *n, int val);
void storeSorted(struct Node *n, int *arr, int *pos);
void bstDestroy(struct Node *n);

int main()
{
int arr[] = { 10, 5, 8, 20, 16, 70, 50, 9 };
int n = sizeof(arr) / sizeof(arr[0]);

bstSort(&arr, n);

for (int ii = 0; ii < n; ii++)
printf("%d\n", arr[ii]);

getchar();
return 0;
}

void bstSort(int *arr, int n)
{
struct Node *root = NULL;

// root = insert(root, arr[0]);

for (int i = 0; i < n; i++)
insert(root, arr[i]);

storeSorted(root, arr, &arr[0]);
bstDestroy(root);
}

struct Node *insert(struct Node *n, int val)
{
if (n == NULL) {
n = malloc(sizeof(struct Node));
(n)->left = NULL;
(n)->val = val;
(n)->right = NULL;
} else {
if (val < n->val)
n->left = insert(n->left, val);
else if (val > n->val)
n->right = insert(n->right, val);
}

return n;
}

void storeSorted(struct Node *n, int *arr, int *pos)
{
if (n != NULL) {
storeSorted(n->left, arr, pos);
arr[*pos] = n->val;
storeSorted(n->right, arr, pos);

}
}

void bstDestroy(struct Node *n)
{
if (n == NULL)
return;
if (n->left != NULL)
bstDestroy(n->left);
if (n->right != NULL)
bstDestroy(n->right);
free(n);
return;
}```
Now I have only one problem left.
The code above works and it creates the tree structure as needed, the only thing is that in the storeSorted function the array is sorted but it remains there.

When I go back to the top of the code it is not sorted so I might need to do some more research.

1. You don't need the for loop or getchar() in your main function.
2. Your bstSort function is incorrect.
3. You don't increment the position of the array when storing the inorder traversal in arr
4. You don't print out the inorder values of the BST in your bstDestroy function and you don't need the return statement.
5. You don't insert the new node properly in your insert function.

Try something like this:

Code:
```#include <stdio.h>
#include <stdlib.h>

struct Node {
int val;
struct Node *left, *right;
};

void bstSort(int *arr, int n);
struct Node *insert(struct Node *n, int val);
void storeSorted(struct Node *n, int *arr, int *pos);
void bstDestroy(struct Node *n);

int main()
{

int arr[] = { 10, 5, 8, 20, 16, 70, 50, 9 };
int n = sizeof(arr) / sizeof(arr[0]);

bstSort(&arr, n);
return 0;
}

void bstSort(int *arr, int n)
{
struct Node *root = NULL;

root = insert(root, arr[0]);

for (int i = 1; i < n; i++)
insert(root, arr[i]);

int i = 0;
storeSorted(root, arr, n);
printf("BST is as follows: ");
bstDestroy(root);
}

struct Node *insert(struct Node *n, int val)
{
if (n == NULL) {
// perform binary tree insertion
struct Node *n = (struct Node*)malloc(sizeof(struct Node));
n->val = val;
n->left = NULL;
n->right = NULL;
return n;

}
// right insertion
if(val > (n->val)){
n->right = insert(n->right, val);
}
// left insertion
else{
n->left = insert(n->left, val);
}
return n;
}

void storeSorted(struct Node *n, int *arr, int *pos)
{
int i = pos++;
if (n != NULL) {
storeSorted(n->left, arr, i);
arr[i] = n->val;
storeSorted(n->right, arr, i);

}
}

void bstDestroy(struct Node *n)
{
if (n != NULL){
bstDestroy(n->left);
printf("%d ", n->val);
bstDestroy(n->right);
}
free(n);
}```

9. Originally Posted by masterxfile
Code:
`bstSort(&arr, n);`
When passed as an argument, an array is converted to a pointer to its first element. Therefore, you should have written:
Code:
`bstSort(arr, n);`
&arr actually results in a pointer to the entire array, i.e., int(*)[8] instead of int*

Originally Posted by snoopfrogg
You don't need the for loop or getchar() in your main function.
While it is true that getchar() is unnecessary, the for loop is a perfectly fine way to print the elements of the array so as to show they have been sorted.

Originally Posted by snoopfrogg
You don't print out the inorder values of the BST in your bstDestroy function
That's perfectly fine. The purpose of bstDestroy is to clean up the resources used to create the binary search tree, not to print anything. In fact, it is a rather bad habit to try and print from such a function: if you wanted to print a binary tree with in-order traversal, then write a function for that purpose rather than piggyback on a function with an entirely different purpose (i.e., functions should do one thing and do it well). But that would be unnecessary too (and against the instructions): the right place to print is after calling bstSort, to demonstrate that the array has been sorted.

Originally Posted by snoopfrogg
Code:
`struct Node *n = (struct Node*)malloc(sizeof(struct Node));`
It is not necessary to cast the return value of malloc, and since there is a parameter named n, it is not a good idea to have another variable named n hide that existing variable in an inner scope. masterxfile's code is better in this regard.

It is also generally good practice to check that malloc did not return a null pointer.

10. Originally Posted by snoopfrogg
Try something like this:

Code:
```#include <stdio.h>
#include <stdlib.h>

struct Node {
int val;
struct Node *left, *right;
};

void bstSort(int *arr, int n);
struct Node *insert(struct Node *n, int val);
void storeSorted(struct Node *n, int *arr, int *pos);
void bstDestroy(struct Node *n);

int main()
{

int arr[] = { 10, 5, 8, 20, 16, 70, 50, 9 };
int n = sizeof(arr) / sizeof(arr[0]);

bstSort(&arr, n);
return 0;
}

void bstSort(int *arr, int n)
{
struct Node *root = NULL;

root = insert(root, arr[0]);

for (int i = 1; i < n; i++)
insert(root, arr[i]);

int i = 0;
storeSorted(root, arr, n);
printf("BST is as follows: ");
bstDestroy(root);
}

struct Node *insert(struct Node *n, int val)
{
if (n == NULL) {
// perform binary tree insertion
struct Node *n = (struct Node*)malloc(sizeof(struct Node));
n->val = val;
n->left = NULL;
n->right = NULL;
return n;

}
// right insertion
if(val > (n->val)){
n->right = insert(n->right, val);
}
// left insertion
else{
n->left = insert(n->left, val);
}
return n;
}

void storeSorted(struct Node *n, int *arr, int *pos)
{
int i = pos++;
if (n != NULL) {
storeSorted(n->left, arr, i);
arr[i] = n->val;
storeSorted(n->right, arr, i);

}
}

void bstDestroy(struct Node *n)
{
if (n != NULL){
bstDestroy(n->left);
printf("%d ", n->val);
bstDestroy(n->right);
}
free(n);
}```
Your code works perfectly except one problem, the array is not getting sorted in the storeSorted function.

I have tried different options but all give the same result. If you print back the array you will see all messed up data. Any ideea?

I did a print to test and the result is below:

value in n 5 - OK
value in pointer 5 - OK
value of pointer 0 - OK
value in n 8 - OK
value in pointer 8 - OK
value of pointer 1 - OK
value in n 9 - OK
value in pointer 9 - OK
value of pointer 2 - OK
value in n 10 - OK
value in pointer 10 - OK
value of pointer 0 - Wrong
value in n 16 - OK
value in pointer 16 - OK
value of pointer 1- Wrong
value in n 20 - OK
value in pointer 20 - OK
value of pointer 1- Wrong
value in n 50 - OK
value in pointer 50 - OK
value of pointer 2- Wrong
value in n 70 - OK
value in pointer 70 - OK
value of pointer 2- Wrong

As you can see at some point the pointer goes back to zero and is replacing the values inside. This drives me crazy

11. It should have been:
Code:
```void storeSorted(struct Node *n, int *arr, int *pos)
{
if (n) {
storeSorted(n->left, arr, pos);
arr[(*pos)++] = n->val;
storeSorted(n->right, arr, pos);
}
}```
Also, the current position was correctly declared in bstSort, but unused, so you need to fix that too. I would rename it pos instead of i.

Pay attention to the compiler warnings.

12. Code:
```struct Node *insert(struct Node *n, int val)
{
if (n == NULL) {
// perform binary tree insertion
struct Node *n = (struct Node*)malloc(sizeof(struct Node));
n->val = val;
n->left = NULL;
n->right = NULL;
return n;
...```
I think that what you are trying to do is...
Code:
```if (n == NULL) {
// perform binary tree insertion
/* You want a new node, not "n" as n is an argument to the function */
struct Node *newNode = malloc(sizeof(*newNode));
/* Test for fail */
if (*newNode  != NULL) {
newNode ->val = val;
newNode ->left = NULL;
newNode ->right = NULL;
}
/* Will return NULL if failed */
return newNode;
...```
I've removed the cast from your malloc, as it is not needed and can hide if you've forgotten stdlib.h

Casting malloc - Cprogramming.com

You also need to handle if val == n->val. Do you really want to insert a duplicate?

13. Click_here: you're supposed to check if newNode is a null pointer, not if *newNode is a null pointer

The reuse of the formal argument n is arguably okay (yes, pun), but what snoopfrogg did was to create a new variable named n in an inner scope, hence shadowing the parameter.

Originally Posted by Click_here
You also need to handle if val == n->val. Do you really want to insert a duplicate?
masterxfile's code didn't handle that, but that's handled by snoopfrogg's fix. If duplicates are allowed in the array, then surely they are allowed in the binary search tree.

14. Whoops - I'm just being lazy and not running the code before posting.

15. I solved the problem, now all the functions are working properly.

All I had to do is create a pointer to 0 and call the function using it, then increment that pointer each time I am storing a value in the array.
Code:
```    if (n != NULL) {
storeSorted(n->left, arr, pos);
arr[(*pos)++] = n->val;
storeSorted(n->right, arr, pos);
}
```
Thank you all for the tips.