Binary Search Tree to store objects by object ID

Question

I'm trying to create a binary search tree that would be used to insert my Packet objects'. It holds information like partId, description, price, and partCount. It's a basic binary search tree. Could you take a look and tell me if there's nothing odd in the code? Because I'm trying to brush up on my BST. Please give me your comments and reviews.

I'm not doing anything complicated, just simple BST. I haven't done C++ in months, trying to review everything again.

This is my testing program:

#include <iostream>
#include "BST.h"
#include "Packet.h"

using namespace std;

int main() {
    BST test1;
    cout << "-------------------------------------------------------" << endl;
    cout << "Testing BST" << endl;
    cout << "-------------------------------------------------------" << endl;
    Packet packetTest(123, "This is a packet of cheese.", 12.95, 10);
    Packet packetTest1(321, "This is a packet of cheese.", 12.95, 10);
    Packet packetTest2(456, "This is a packet of cheese.", 12.95, 10);
    Packet packetTest3(7, "This is a packet of cheese.", 12.95, 10);
    Packet packetTest4(119, "This is a packet of cheese.", 12.95, 10);
    Packet packetTest5(456, "This is a packet of cheese.", 12.95, 10);
    test1.insert(packetTest);
    test1.insert(packetTest1);
    test1.insert(packetTest2);
    test1.insert(packetTest3);
    test1.insert(packetTest4);
    test1.insert(packetTest5);
    test1.preorderTraversal();
    system("pause");
}

Here's my BST.h:

#pragma once

#include <string>
#include <iostream>
#include <stack>
#include "Packet.h"
using namespace std;

class Node
{
    friend class BST;
public:
    Node() : packet(packet), rlink(nullptr), llink(nullptr) {}
    ~Node() {}

private:
    Packet *packet;
    Node *rlink, *llink;
};

class BST {
public:
    BST();
    void BST::insert(Packet& packet);
    void BST::insert(Node* &p, Node *newNode);
    void preorderTraversal() const;
private:
    Node *root;
    void preorderTraversal(const Node *p) const;
};

The BST.cpp Careful with this part, I might have done some things here, can you take an extra look here?:

#include "BST.h"

BST::BST() : root(nullptr) {}

void BST::insert(Packet& thisPacket) {
    Node *newNode = new Node;
    newNode->packet = &thisPacket;
    insert(root, newNode);
}

void BST::insert(Node *&p, Node *newNode)
{
    if (p == nullptr)
        p = newNode;
    else if (p->packet->getPartId() < newNode->packet->getPartId())
        insert(p->llink, newNode);
    else
        insert(p->rlink, newNode);
}

void BST::preorderTraversal() const {
    if (root == nullptr)
        cerr << "There is no tree.";
    else
    {
        preorderTraversal(root);
    }
}

void BST::preorderTraversal(const Node *p) const {
    if (p != nullptr) {
        cout << p->packet->getPartId() << " ";
        preorderTraversal(p->llink);
        preorderTraversal(p->rlink);
    }
}

And finally Packet.h:

#pragma once
#include <string>

using namespace std;

class Packet {
public:
    Packet(int partId, string description, double price, int partCount) :
        partId(partId), description(description), price(price), partCount(partCount) {}
    int getPartId() const {return partId;}

private:
    int partId;
    string description;
    double price;
    int partCount;
};

Answer 1

Don't import the standard namespace

Namespace std is a large, and growing, namespace. Do you know every identifier in it? Including the ones to be defined in C++20 and beyond? Bringing all its names into the global namespace not only eliminates the benefits of using namespaces, but also has the potential to silently and subtly change the meaning of your program in future (e.g. by supplying an unambiguously better match for one of your function calls).

It's an especially bad practice in a header file, as now you're inflicting the breakage on every single user of that header file, with no way to correct it.

Syntax errors

This doesn't compile:

class BST {
    void BST::insert(Packet& packet);
    void BST::insert(Node* &p, Node *newNode);
};

Remove the extra qualification from the members.

Self-initialization

It's useless to initialize packet using its own (uninitialized) value here:

Node() : packet(packet), rlink(nullptr), llink(nullptr) {}

Memory leak

I'm not sure how you exercised the test program, but when I ran it with Valgrind, it immediately told me about this leak:

==31705== HEAP SUMMARY:
==31705==     in use at exit: 144 bytes in 6 blocks
==31705==   total heap usage: 20 allocs, 14 frees, 74,208 bytes allocated
==31705== 
==31705== 144 (24 direct, 120 indirect) bytes in 1 blocks are definitely lost in loss record 6 of 6
==31705==    at 0x4835DEF: operator new(unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==31705==    by 0x10A276: BST::insert(Packet&) (222481.cpp:54)
==31705==    by 0x10A744: main (222481.cpp:104)

If we're owning raw pointers, we need to be absolutely sure every new is paired with exactly one delete. It's much better to use the smart pointers provided in <memory> than to try to do this on our own.

Encapsulation

Node isn't part of the public interface. If we make it a private struct within BST, then BST gets full access (not needing a friend declaration), but no other code does. That's what we really want.

Flexibility

preorderTraversal() hard-codes the action to take for each node (printing it). What we want is to use the Visitor pattern, where we pass the action as a parameter to the call.

Ease of use

We've made the interface unnecessarily hard to use, by insisting that packets are passed by reference. This means that the calling code is obliged to ensure that every packet outlives the tree. If packets could be copied/moved to the tree, then it would be much easier for other code to use it.

Clean output

Is there any reason not to end the output with a newline? It's very annoying when commands leave the next shell prompt dangling halfway across the terminal.

Portability

Don't use std::system() if you can avoid it:

sh: 1: pause: not found

Even if such a program was present in my search path, how do you know what function it performs? I'm guessing it's a program that waits forever (like sleep inf on a GNU system). That sounds like a real obstruction to using the test (e.g. it will prevent make test from ever completing successfully). Is that really what's desired?

Answer 2

Stop using namespace std;

Having using namespace std;, especially in a header file is considered bad practice. This Stack Overflow post explains the reasoning quite well. In your case it's especially unnecessary since you do not even use something from this namespace in BST.h and only std::string in Packet.h.

Unnecessary includes

Again BST.h. There are a lot of unused includes in there. The only one that might serve a purpose would be Packet.h which could easily be replaced by a forward declaration. Most of the include should go to the corresponding .cpp file.

The BST

I'm not sure about the interface. If your intended usage is to pass packages by reference, it would be desirable to declare BST::insert(Node *&p, Node *newNode) as private, similar to the public and private versions of preorderTraversal. preorderTraversal might also be better called printPreorder or something like this since it only prints the nodes and does not allow to access them.

There is also a small memleak in insert since those Node*s created with Node *newNode = new Node; will never get deleted. valgrind confirms this. As @TobySpeight rightfully pointed out in his comment and detailed in his answer, one can argue if leaking all of the tree's nodes should really be considered as a "small" memleak. A possible solution for this is to use smart pointers from <memory>. There is a good overview in this blog post by Herb Sutter on which type of smart pointer (e.g. std::unique_ptr or std::shared_ptr) as well as the type of parameter passing (by-reference vs. by-value) should be used to express a certain "meaning".