Binary Search Tree to store objects by object ID
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".