solved 'Implement Trie (Prefix Tree)' on leetcode https://leetcode.com/problems/implement-trie-prefix-tree/

trie.cc

struct TrieNode {
  TrieNode *next = nullptr;
  TrieNode *child = nullptr;
  char val = 0;
  // Indicating end of word.
  bool terminal = false;
};

class Trie {
 public:
  Trie() { root = new TrieNode(); }

  // Inserts a word into the trie.
  void insert(string word) {
    int curr_level = 0, len = word.length();
    TrieNode *curr_level_node = root;
    while (curr_level < len) {
      TrieNode *next_level_node =
          findChildNode(curr_level_node, word[curr_level]);
      if (!next_level_node) {
        // If not found, break and begin inserting.
        break;
      } else {
        // Otherwise follow the link.
        ++curr_level;
        curr_level_node = next_level_node;
      }
    }

    while (curr_level < len) {
      curr_level_node = insertChildNode(curr_level_node, word[curr_level]);
      ++curr_level;
    }
    // Mark end of word.
    curr_level_node->terminal = true;
  }

  // Returns if the word is in the trie.
  bool search(string word) {
    TrieNode *curr_level_node = root;
    for (int i = 0, len = word.length(); i < len; ++i) {
      TrieNode *next_level_node = findChildNode(curr_level_node, word[i]);
      if (!next_level_node) {
        return false;
      } else {
        curr_level_node = next_level_node;
      }
    }
    return curr_level_node->terminal;
  }

  // Returns if there is any word in the trie
  // that starts with the given prefix.
  bool startsWith(string prefix) {
    TrieNode *curr_level_node = root;
    for (int i = 0, len = prefix.length(); i < len; ++i) {
      TrieNode *next_level_node = findChildNode(curr_level_node, prefix[i]);
      if (!next_level_node) {
        return false;
      } else {
        curr_level_node = next_level_node;
      }
    }
    return true;
  }

  ~Trie() {
    // Recursively delete nodes.
    deleteNode(root);
  }

 private:
  static void deleteNode(TrieNode *subroot) {
    if (subroot->next) {
      deleteNode(subroot->next);
    }
    if (subroot->child) {
      deleteNode(subroot->child);
    }
    delete subroot;
  }

  static TrieNode *findChildNode(TrieNode *subroot, char c) {
    TrieNode *child = subroot->child;
    while (child && child->val <= c) {
      if (child->val == c) {
        return child;
      } else {
        child = child->next;
      }
    }
    // Didn't find the subroot matching c.
    return nullptr;
  }

  static TrieNode *insertChildNode(TrieNode *subroot, char c) {
    TrieNode *child = subroot->child, *inserted;
    if (!child || child->val > c) {
      // Insert under subroot.
      subroot->child = new TrieNode;
      inserted = subroot->child;
      inserted->val = c;
      inserted->next = child;
    } else {
      // Find an appropriate place to insert.
      while (child->next) {
        if (child->next->val < c)
          child = child->next;
        else
          break;
      }
      auto next = child->next;
      child->next = new TrieNode;
      inserted = child->next;
      inserted->val = c;
      inserted->next = next;
    }

    return inserted;
  }

  TrieNode *root;
};

// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");