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

Question

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

Any advice is welcome.

Answer 1

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)
    //Google about virtual functions for abstract classes (pure virtual too)
    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.

Also, I recommend you to read the Google C++ Code Style

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.

Answer 2

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.