Optimising a custom tree data structure
Why do you have m_parent? I don't think there are any reasonable operations on a trie that require a parent pointer in each node, and removing it can reduce the space used a lot.



I don't love using a depth argument in add. I'd use the following instead:

void add(const std::string&amp; key, const T&amp; value) {
  return add(key.data(), key.size(), value);
}
void add(const char *key, const T&amp; value) {
  return add(key, std::strlen(key), value);
}
void add(const char* key, std::size_t len, const T&amp; value);  // impl below




I suggest that you keep the children sorted by m_key. Write a comparison functor like so:

struct KeyLessThan {
  bool operator()(const PrefixTree&amp; l, const PrefixTree&amp; r) const {
    return l.m_key &lt; r.m_key;
  }
  bool operator()(const PrefixTree&amp; tree, char c) const {
    return l.m_key &lt; c;
  }
};


Now you can rewrite add like this (using the signature above):

void PrefixTree::add(const char* key, std::size_t len, const T&amp; value) {
  assert(len &gt;= 0);
  if (len == 0) {
    m_value = value;
    return;
  }
  auto it = std::lower_bound(begin(m_branches), end(m_branches),
                             *key, KeyLessThan());
  if (it == end || it-&gt;m_key != *key) {
    it = m_branches.emplace(it, *key);
  }
  it-&gt;add(key + 1, len - 1, value);
}


The size of m_branches is bounded to be quite small (256 elements in theory; in practice if you're doing English words only it'll be 26 or 52 at the root and much smaller in interior nodes), so this should be quite fast, and it'll make find faster.



Speaking of m_branches, m_children would be a more usual name for it.



It's not really clear that you want find to return a T*; it's odd to give out handles to internal memory in a data structure like this. I would make the signature one of

const T* find(const std::string&amp; key) const
std::pair&lt;bool, const T&amp;&gt; find(const std::string&amp; key) const


or

std::pair&lt;bool, T&gt; find(const std::string&amp; key) const


(if you have access to a C++14 implementation, even better is 

std::optional&lt;T&gt; find(const std::string&amp; key) const


Whichever you choose, use the same overloads as with add for const char *, etc.



It is very weird to me to see an #include that's not at the top of the file, and to see printfs in the middle of a C++ file.