1
\$\begingroup\$

Here is a code for BST that I have written , that does not use pass by reference. Help me to find flaws in its design. Also I do not like the function getReqNodes, can it be made more elegant.

#include <iostream>
using namespace std;

struct node {
    int data;
    node* left = nullptr;
    node* right = nullptr;
    node(int d , node *l = nullptr, node *r = nullptr){
        data = d;
        left = l;
        right = r;
    }
};
node* insertVal(node* n, int val) {
    if (n == nullptr) {
        n = new node(val);
        n->data = val;
        return n;
    }
    else if (val < n->data){
        return new node(n->data, insertVal(n->left,val), n->right);
    }
    else if(val > n->data) {
        return new node(n->data, n->left, insertVal(n->right, val)); 
    } 
    else{
        return new node(val, n->left, n->right);
    }
}
int minVal(node* n) {
    if (n == nullptr) return -10000;
    else if (n->left == nullptr) return n->data;
    else return minVal(n->left);
}


node* getReqNodes(node *t, node *q){
    if(q == nullptr){return t;}
    else{
        t = insertVal(t,q->data);
        t = getReqNodes(t,q->left);
        t = getReqNodes(t,q->right);
        return t;
    }
}

node* removeVal(node *n, int v){
    if (n == nullptr){return n;}
    else if(v < n->data){
        return new node(n->data, removeVal(n->left,v), n->right);
    }
    else if(v > n->data){
        return new node(n->data, n->left, removeVal(n->right, v));
    }
    else{
        node *j = n;
        //attaching right subtree to the left subtree
        node *p = getReqNodes(n->left, n->right);
        delete j;
        return p;
    }
}

void printTree(node* n) {
    if (n == nullptr) { return; }
    printTree(n->left);
    cout << n->data << " ";
    printTree(n->right);
}

int main() {
    node* p = nullptr;
    for(int i = 0; i < 15; ++i){
        p = insertVal(p, rand()%15);
    }
    printTree(p);cout<<endl;cout<<endl;
    node *foo = removeVal(p, 149);
    printTree(foo);
    return 0;

}
\$\endgroup\$
1
  • \$\begingroup\$ This is C code. The only C++ thing is your usage of std::cout. You need to work on encapsulation and how classes work. \$\endgroup\$ Apr 21, 2021 at 23:04

2 Answers 2

1
\$\begingroup\$

General Observations

The code compiles and runs in Visual Studio 2019 on Windows 10.

The vertical spacing is inconsistent and could be improved.

The code could be reusable if the Binary Search Tree was made into a class.

The unit testing in main could be more effective if know values were used first and then a second test with random number generated. The test of removeVal() currently only tests a value that is never in the BST, the function does work because I changed the value in the test.

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.

Function and Variable Naming

Generally the function names are fairly good, there is one exception, it isn't clear to me from the name what getReqNodes() is supposed to do. In main it might be better to have a variable called bst or root rather than p.

Random Number Generation

It would be better to use C++ random number generators rather than the old C library function rand() function, see EDIT 2 in the first answer to this stack overflow question. Currently the random number generator is not random because it is never seeded with a value by calling srand().

One Statement Per Line

The code contains multiple lines where there is more than one statement such as:

    printTree(p); cout << endl; cout << endl;

This makes the code harder to read, understand and maintain, always remember that you may not be the only person that needs to edit the code.

There are 2 other issues with that line, that std::endl flushes the output which affects the performance of the program so using:

    std::cout << "\n";

might be a better option. The second is that if a string such as "\n" is used then the string "\n\n" can be used to output 2 new lines, decreasing the number of statements necessary, although this is also possible:

    std::cout << std::endl << std::endl;
\$\endgroup\$
1
\$\begingroup\$

The n->data = val; statement in insertVal is unnecessary, because the constructor for node already populates the data field. With that line removed, you can remove the assignment to n and replace all 3 statements with return new node(val);.

However, the bigger issue is a memory leak. insertVal should only allocate a new node at most once for any insert, but as it is it will allocate a new node for every level of the tree it passes. Even in the case of inserting a duplicate node, the existing node is leaked and a new node allocated.

The code to insert on the left should replace the current left node with the value returned from the recursive call to insertVal:

    if (val < n->data){
        n->left = insertVal(n->left, val);
        return n;
    }

With a similar changes to inserting on the right, and returning the current node when the you find the value being inserted, will get rid of the leak.

You can also replace the recursive insertion with a loop based one.

Similar change can be made to `removeVal, which should not be allocating any nodes at all, just reusing the existing ones in the tree.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.