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

Question

I'm trying to write a program that sorts integer elements of an array, using a Binary Search Tree(BST) as support data structure. The idea is that once the array is given, then it is possible to use a BST to sort his element; for example:

if my array is: {120, 30, 115, 40, 50, 100, 70}

then I build a BST like this:

Once I have this BST, I can do an inorder tree traversal to touch every node in order, from the lowest to the highest element and modify the array. The result would be a sorted array {30, 40, 50, 70, 100, 115, 120}

I wrote this code and I don't understand where is the error I made. It compiles without any error, but obviously there is something wrong with it:

#include<iostream>
using namespace std;

struct Node
{
    int label;
    Node* left;
    Node* 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
{
    i=0;
    if(!tree) return 0;
    i += insertIntoArray(arr, tree->left, i) +1;
    arr[i] = tree->label;
    i += insertIntoArray(arr, tree->right, i) +1;
    return i;

}

int main()
{
    Node* maintree;
    maintree = NULL;
    int num;
    cin>>num;
    int arr[num];
    for(int i=0; i<num; i++){    //initialize array with num-elements
     cin>>arr[i];
    }
    insertArrayTree(arr, num, maintree);    //insert elements into BST
    int index;
    insertIntoArray(arr, maintree, index);  //modify array sorting his elements using the BST

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

    return 0;
}

I hope that my question is clear enough. Any help/advice would be appreciated!

Thanks :)

I'm just glancing at your code, but why does insertIntoArray immediately set its i argument to 0? — Brady Dean
– Brady Dean, Commented Apr 7, 2020 at 2:23
@BradyDean I was trying to figure out how to insert the elements of BST in the right positiom of array, but seems not working now that I'm looking too at the function insertIntoArray. Maybe would it work if it returns -1 instead of 0 when tree==NULL ? (Sorry about my english, hope it is clear) — Vittorio A.
– Vittorio A., Commented Apr 7, 2020 at 2:39
I about have your code working, I'm just trying to figure out insertIntoArray. You forgot to check if x == tree->label in insertSearchNode also. — Brady Dean
– Brady Dean, Commented Apr 7, 2020 at 2:40
Nice start. When you get it working you should get a code review at: codereview.stackexchange.com PS. They will only review working code so it needs to be fixed first. — Loki Astari
– Loki Astari, Commented Apr 7, 2020 at 4:12
Yes, a nice start indeed. But note, a BST is generally not something used to "sort" data, the BST is a data structure that holds the data in a sorted order to begin with, so all that is needed is an in-order traversal to output the data in sort order. If you don't need an array, there is no need to use one just to fill the BST. A std::map is generally implemented as a Red-Black tree. If you are using the array, you can simply sort it with std::sort. Lots of options. — David C. Rankin
– David C. Rankin, Commented Apr 7, 2020 at 4:42

Loki Astari · Accepted Answer · 2020-04-07 04:34:58Z

2

The only thing that seems to be wrong is the insertIntoArray().

The first issue is that you are passing an unitialized variable as a parameter:

int index;
insertIntoArray(arr, maintree, index);

Why. You are starting to fill the array at zero so pass zero (and get rid of the index variable).

insertIntoArray(arr, maintree, 0);

I could not quite decipher your version of insertIntoArray(). But this version seems to work.

int insertIntoArray(int arr[], Node* tree, int i)
{
    // If you fall of a leaf then there is nothing to do.
    // So simply return the index as it has not changed.
    if (!tree) {
        return i;
    }


    // Since it is a BST we always go left first.
    // The return value is where we have reached when we
    // have inserted all the left values. 
    i = insertIntoArray(arr, tree->left, i);

    // Now put the current value in and increment the index position.
    arr[i] = tree->label;
    ++i;

    // Now do the right sub-tree.
    i = insertIntoArray(arr, tree->right, i);

    // Return the point index we have reached so far.
    return i;
}

OK. So it should work. BUT that does not mean this is all good C++ code. You really should get this code reviewed.

answered Apr 7, 2020 at 4:34

Loki Astari

267k87 gold badges344 silver badges575 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Vittorio A. Over a year ago

My insertIntoArray function was clearly not working at all, thank you for the explanation. May I ask you what do you mean with code review and what are the benefits of it? I'm new in coding and any advice is really apprecciated.

Loki Astari Over a year ago

@VittorioA. Code review is a processes that all professionals use to check your code. It is where other developers read your code and point out: 1) Errors 2) Bad practice 3) Better techniques 4) Design patterns that could be used 5) Conventions used in the language (idioms).

Brady Dean · Accepted Answer · 2020-04-07 03:31:00Z

1

So I modified quite a bit of the code. First thing to notice is I'm using Node** instead of Node* &. This is a pretty common idiom when dealing with trees and traversal algorithms. Reason being is you need to be able to modify the pointer being passed in (I take it this is why you used Node* &, you could also do it that way). The big difference with insertIntoArray is that int i becomes int* i, that way each call to insertIntoArray can share the same incrementing index. I also added a touch of memory management.

I also need to warn you that int arr[num]; is a variable length array (VLA) and is not standard C++. std::vector is the way you should go. (in fact it makes this problem easier because you can append easily)

#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) {
        if (x < (*tree)->label)
            insertSearchNode(&(*tree)->left, x);
        else
            insertSearchNode(&(*tree)->right, x);
    } else {
        *tree = new Node;
        (*tree)->label = x;
        (*tree)->right = NULL;
        (*tree)->left = NULL;
    }
}

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]);
}

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

int main()
{
    Node* maintree = NULL;

    int num;
    cin >> num;

    int arr[num];

    for (int i = 0; i < num; i++)    //initialize array with num-elements
        cin >> arr[i];

    insertArrayTree(arr, num, &maintree);    //insert elements into BST
    int index = 0;
    insertIntoArray(arr, &maintree, &index);  //modify array sorting his elements using the BST

    delete maintree;

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

edited Apr 7, 2020 at 3:31

answered Apr 7, 2020 at 3:25

Brady Dean

3,6115 gold badges30 silver badges50 bronze badges

2 Comments

Vittorio A. Over a year ago

Thank you very much for your solution! So basically Node** and Node*& are both correct to use? Which is the benefit of choosing one instead other? Also, why vector would make this problem easier?

Brady Dean Over a year ago

You don’t need to make a running index to insert into a vector. You can accomplish the same thing with either a double pointer or pointer reference in your code.

Collectives™ on Stack Overflow

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

2 Answers 2

2 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related