Binary Search Tree to store objects by object ID 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 &lt;iostream&gt;
#include "BST.h"
#include "Packet.h"

using namespace std;

int main() {
    BST test1;
    cout &lt;&lt; "-------------------------------------------------------" &lt;&lt; endl;
    cout &lt;&lt; "Testing BST" &lt;&lt; endl;
    cout &lt;&lt; "-------------------------------------------------------" &lt;&lt; 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 &lt;string&gt;
#include &lt;iostream&gt;
#include &lt;stack&gt;
#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&amp; packet);
    void BST::insert(Node* &amp;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&amp; thisPacket) {
    Node *newNode = new Node;
    newNode-&gt;packet = &amp;thisPacket;
    insert(root, newNode);
}

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

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

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


And finally Packet.h:

#pragma once
#include &lt;string&gt;

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;
};
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 *&amp;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 &lt;memory&gt;. 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".