You can avoid a lot of ownership problems by using:

std::unique_ptr<Node<T>> root;

and also simplify a lot of logic into loops by using:

enum { LEFT, RIGHT };
std::unique_ptr<Node<T>> children[2];

(but still Node<T> *parent; being because it's backwards, not owning)

You should only use operator < (sometimes with arguments swapped or with the result negated), never operator ==: they might not be related.

__Data_Structures__BinarySearchTree__ is not a legal identifer for users, it is reserved for the implementation since it has two underscores in a row and/or an initial underscore followed by a capital letter. I avoid this by using #pragma once since it is supported by all compilers.

#include <cstdio> instead of #include <stdio.h>

srand seeds a poor random number generator, and time is a very predictable seed. But you don't actually call rand in this code.

I have never had cause to use anything but in-order traversals, and those are implemented by iterators.

All of your #pragma mark is really distracting. Most tools are sensible enough to use comments for documentation grouping, but most of the time that is only needed on a very coarse basis at namespace scope.

In your many of your functions, you are wasting stack with recursion unless the compiler performs TCE.

You are missing copy/move constructor/assignment operators.

This is not a self-balancing binary tree, so it will degenerate to a linked list on certain common inputs.

In addition to the answers you have already received.

Use the right headers

Prefer the C++ headers for C functions when you write C++ code.

I.e:

#include <cstdio>

Weird use of typedef

I'm not really a fan of how you use typedef here, the type int is the default backing type and it doesn't really matter which type you have in your case. As you're using C++11 you might as well use enum class.

Your enum definition should just be:

enum class TraversalType
{
    InOrder,
    PreOrder,
    PostOrder
};

A classic case of KISS.

Use an object oriented design

You currently use Node as a plain data structure. But if you delegate some of the work to the node class, you'll see that your code will simplify. For example search is a good candidate. While we're at it, your code requires that you have both operator < and operator == for the key type. You can rewrite your search logic like this to avoid this requirement:

Node* search(const T &a_key)
{
    if (a_key < key) {
        return left ? left->search(a_key) : nullptr;
    }
    else if (key < a_key){
        return right? right->search(a_key) : nullptr;
    }
    else{
        return node;
    }
}

as long as operator < defines a partial ordering.

An added benefit of the above implementation is that instead of nullptr you can return left or right, you can use then use this to implement your insert function. How is left as an exercise for the reader.

Any method where you find yourself using node-> frequently is a good candidate to move into the Node class.

There is no need to use a nested class template for Node. Node should use the same template parameters as BinarySearchTree. After all, you will not need to have a tree of Node<int> in a BinarySearchTree<float>.

You can just use:

struct Node
{
    T key;

    Node* left = nullptr;
    Node* right = nullptr;
    Node* parent = nullptr;
};

The functions minimum and maximum don't take into account the possibility that the tree is empty.

T minimum(Node* node)
{
    // If node is nullptr, all three lines are problematic.
    if (node->left == nullptr)
        return node->key;

    return minimum(node->left);
}

T maximum(Node* node)
{
    // If node is nullptr, all three lines are problematic.
    if (node->right == nullptr)
        return node->key;

    return maximum(node->right);
}

Since these functions are recursive, the check for whether the tree is empty should not be added here. Instead, they should be added in the public functions of the same name.

T minimum()
{
    if ( root == nullptr )
    {
        // Throw some kind of exception.
    }
    return minimum(root);
}

T maximum()
{
    if ( root == nullptr )
    {
        // Throw some kind of exception.
    }
    return maximum(root);
}

Remove

I find it interesting that you have a special case for removing the root where if it has one child, you reroot the tree on the child. That is actually a good move because it always reduces the tree height by one, whereas moving a successor up to the root doesn't necessarily reduce the tree height.

But then right after that code, you don't choose to do the same trick for an interior node. If an interior node to be removed has only one child, then you should do the same thing and move its child up one level replace the node being removed. Not only does it reduce the subtree height, it's also faster than searching for a successor.

RemoveAll

Although the function is short and simple, I have two problems with it.

1. Right now the removal takes \$O(n\log n)\$ time due to finding successors to replace the root. It would be faster to remove leaf nodes instead of the root node. For example you could remove in a postorder traversal fashion, which would take only \$O(n)\$ time.
2. The recursion depth of this function is \$O(n)\$, which means it could overflow your stack. Now a good compiler will perform a tail recursion optimization and make this problem go away. But it's still something you should keep in mind when you write any recursive function.

Recursion

As mentioned above, your removeAll() function uses a tail end recursive call. Usually these kinds of recursions are very easy to rewrite in a non-recursive way (the same way a compiler would optimize it). In your case:

void removeAll()
{
    if (root == nullptr)
        return;

    remove(root->key);
    removeAll();
}

can be transformed into:

void removeAll()
{
    while (1) {
        if (root == nullptr)
            return;

        remove(root->key);
    }
}

which simplifies to:

void removeAll()
{
    while (root != nullptr)
        remove(root->key);
}

But again, remember that I recommend completely rewriting the removeAll() function to delete in a postorder traversal like this:

void removeAll(Node *node)
{
    if (node == nullptr)
        return;

    removeAll(node->left);
    removeAll(node->right);
    delete node;
}

void removeAll()
{
    removeAll(root);
    root = nullptr;
}

I feel like even the above can be made non-recursive, because you have a parent pointer. Here's how you could free the whole tree in a non-recursive function (not tested):

void removeAll()
{
    Node *next;

    for (Node *p = root; p != nullptr; p = next) {    
        if (p->left != nullptr) {
            next = p->left;
            p->left = nullptr;
        } else if (p->right != nullptr) {
            next = p->right;
            p->right = nullptr;
        } else {
            next = p->parent;
            delete p;
        }
    }
}