# Sorting an array using a Binary Search Tree with C++

Given an array of integer (all different from each other), this program creates a BST with the array elements in order to sort them and put them back into the array, using the BST properties.

#include<iostream>
using namespace std;

struct Node
{
int label;
Node* left;
Node* right;

~Node() {
delete left;
delete right;
}
};

void insertSearchNode(Node* &tree, int x)       //insert integer x into the BST
{
if(!tree){
tree = new Node;
tree->label = x;
tree->right = NULL;
tree->left = NULL;
return;
}
if(x < tree->label) insertSearchNode(tree->left, x);
if(x > tree->label) insertSearchNode(tree->right, x);
return;
}

void insertArrayTree(int arr[], int n, Node* &tree)     //insert the array integer into the nodes label of BST
{
for(int i=0; i<n; i++){
insertSearchNode(tree, arr[i]);
}
return;
}

int insertIntoArray(int arr[], Node* &tree, int i)      //insert into the array the node label touched during an inorder tree traversal
{
if(!tree) return i;
i = insertIntoArray(arr, tree->left, i);
arr[i] = tree->label;
i++;
i = insertIntoArray(arr, tree->right, i);
return i;

}

int main()
{
Node* maintree;
maintree = NULL;
int num = 7;
int arr[num] = {120, 30, 115, 40, 50, 100, 70};
insertArrayTree(arr, num, maintree);      //insert elements into BST
insertIntoArray(arr, maintree, 0);        //modify array sorting his elements using the BST

for(int y=0; y<num; y++) cout<< arr[y] << ' ';

return 0;
}


Output:

30 40 50 70 100 115 120


• @S.S.Anne Not sure you really needed to delete all that. – pacmaninbw Apr 7 at 18:10
• @pacmaninbw The information there could be more easily expressed in tags, which is why I edited. The rest of that wasn't really necessary for a review. – S.S. Anne Apr 7 at 18:22
• @pacmaninbw what information could I keep in your opinion? I would like to know so that I can write a better question next time. – Vittorio A. Apr 7 at 19:11
• Use the tags as much as possible because they are searchable. Give an overview of what the code does in text, most reviewers can get a lot from the code. This first attempt was better than many. – pacmaninbw Apr 7 at 19:14

Your code is readable and easy to understand. Said that I would like to make you think about how you handle the operations in your BSTree.

You are building the functions alone, and what that causes is to manually manage these functions and compromise the structure of your tree if accidentally you write something wrong.

You should opt for an Internal management rather than external one. For example:

struct BinaryNode
{
int label_;
Node* left_;
Node* right_;

//having constructors makes you write less code

BinaryNode(Node *left, const int &label, Node *right) :
label_(label), left_(left), right_(right)
{
}

//const [datatype]&
//means to not copy the value of the parameter
BinaryNode(const int &label) :
//nullptr is typesafe use it instead of NULL which is a macro
label_(label), left_(nullptr), right_(nullptr)
{
}

~BinaryNode() {
delete left_;
delete right_;
}
};

class BinarySearchTree
{
private:
BinaryNode *root_;

protected://if some derived class is needed (as an AVLTree)
virtual void Insert(const int &x, Node *node)
{
if (x < node->label_)
if (node->left_ == nullptr)
node->left_ = new BinaryNode(t);
else Insert(t, node->left_);
else if (x > node->label_)
if (node->right_ == nullptr)
node->right_ = new BinaryNode(t);

//If x is in the tree it does not include x again
}

public:
virtual void Insert(const int &x)
{
Insert(x, this->root_);
}
};


Don't misunderstand me, Your code is useful and is pretty (is something good to read). But, manage things externally can be messy.

Hope it helped.

### Edit: What does const int& x means?

const int& x is a constant reference to a value of type int so, when you use it, your function does not copy the sent value, instead it "sees where the value is allocated" takes it in account and then starts the procedure you describe within the function, additionally you cannot modify that value (because it's constant [const])

the main difference is with const [datatype]& you save space. With [datatype] [paramName] you Copy the value which implies allocate the copied value.

If you feel lost in some part read it slowly it has many concepts, and remember practice makes this make sense.

• I don't know if the poster is ready for object oriented programming yet. – pacmaninbw Apr 7 at 18:18
• Ok, I tried to understand your code with my poor knowledge and I understood the main idea. Avoid to write, like you said, functions alone (I imagine them without a sort of protection, if I get right). The code you wrote is sometimes hard to me to understand; for example I don't understand the use of virtual in " virtual void Insert(const int &x, Node *node) " , what does it mean exactly? I read about virtual function and I only understand that it can be useful when it is called for different derived class, but doesn't the obj type itself enough to get the right function? Hope I'm clear enough – Vittorio A. Apr 7 at 19:44
• @Miguel Avila Also, I do not understand the Insert public function too. It received a const int& but then it calls another Insert function with different parameters. At last I don't fully understand the body of the constructor BinaryNode(Node left, const int &label, Node *right). For example: what left_(left) does? It assign the "left" to left_ so that left_ point the same Node as "left" ? Is it some sort of writing shortcut? Sorry about these many questions. – Vittorio A. Apr 7 at 19:52
• The public function is a "facade", it is because you will need to insert elements in your tree recursively but you want to hide that because you always will use the root_ node for that purpose (inserting elements). About the constructor. left_(left) is the way you initialize struct and class members (attributes) here left_ refers to the atribute of BinaryNode and left refers to the parameter you receive in the constructor. – Miguel Avila Apr 7 at 21:52
• Ok now I almost fully understand the code, but I still don't get the "virtual" function (when these are necessary?) and never used a initializer list for the costructor. I will read more documentation on these things. Thanks for the effort to explain everything. – Vittorio A. Apr 8 at 11:48

Overall the code looks good and you seem to have some good programming habits. You need to try to use more of the features available in C++ and the STL.

## Avoid using namespace std;

If you are coding professionally you probably should get out of the habit of using the using namespace std; statement. The code will more clearly define where cout and other identifiers are coming from (std::cin, std::cout). As you start using namespaces in your code it is better to identify where each function comes from because there may be function name collisions from different namespaces. The identifiercout you may override within your own classes, and you may override the operator << in your own classes as well. This stack overflow question discusses this in more detail.

## Variable in Array Declarations

Using a strict C++ compiler the following code does not compile

    int num = 7;
int arr[num] = {120, 30, 115, 40, 50, 100, 70};


Use the std::vector container class. Most or all of the container of the container classes have a size() member that returns the number of items stored in the container. This means if you have to pass the array you only have to pass the container class and not the number of elements in the container.

    std::vector<int> arr = {120, 30, 115, 40, 50, 100, 70};


If you insist on using old style C programming arrays you can get num after the initialization of the array.

    int arr[] = {120, 30, 115, 40, 50, 100, 70};
size_t num = sizeof(arr)/ sizeof(*arr);


Declare num as a constexpr.

    constexpr size_t num = 7;
int arr[num] = {120, 30, 115, 40, 50, 100, 70};


Prefer container classes over old C style arrays. They are easier to use, here's an example updating on of the functions in the code. Note that the std::vector.size() function is not referenced in the following code.

void insertArrayTree(std::vector<int> arr, Node* &tree)     //insert the array integer into the nodes label of BST
{
for (int i: arr)
{
insertSearchNode(tree, i);
}
return;
}


The above for loop is called a ranged for loop.

## Use Modern C++ Constructs

In several places in the code there is the assignment of NULL to pointers. In modern C++ NULL has been replaced by nullptr.

void insertSearchNode(Node* &tree, int x)       //insert integer x into the BST
{
if(!tree){
tree = new Node;
tree->label = x;
tree->right = nullptr;
tree->left = nullptr;
return;
}
if(x < tree->label) insertSearchNode(tree->left, x);
if(x > tree->label) insertSearchNode(tree->right, x);
return;
}


## Possible Bug

The above code does not handle the case where x is already in the tree, in large lists of values there may be duplicates.

## Return from Main()

In a program as simple as this the return 0; statement is not necessary, the compiler will take care of it. The return statement is necessary when the program might exit due to failures return ;. In this case you would need both return 1; and return 0;. It would also be better in this case to include cstdlib and use return EXIT_SUCCESS; and return EXIT_FAILURE; to make the code more readable.

• I will try to avoid the use of namespace. Thank you very much for the tips about the ranged for loop, I did not know about it at all. Then comes the vector structure; I am honestly afraid to use it because I never had the knowledge on how to use it properly. – Vittorio A. Apr 7 at 19:05
• Convert this problem to vectors, then the link I shared for ranged for is a good place for C++ reference. Just keep trying. – pacmaninbw Apr 7 at 19:11
• I woudl add prefer to use size_t num = std::size(arr) rather than size_t num = sizeof(arr)/ sizeof(*arr);` – Martin York Apr 7 at 20:26
• @MartinYork Thank you, I will use that in the future if I need to. – pacmaninbw Apr 7 at 21:05