/**
 * Initialize your data structure here.
 */
/*
STEPS/PSEUDOCODE:
1. Create definition of an instance of Trie
2. example: {str: "", next: {another instance of Trie}}
3. Using binary tree
*/
var Trie = function(text) {
  var trie = {};
  trie.str = text;
  trie.left = null;
  trie.right = null;
  return trie;
};

/**
 * Inserts a word into the trie.
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
  //If word is greater than the last node then insert on leaf node
  //Else insert on left side of lead node
  //Setup base case which is where node.next === null
  //Traverse binary search tree
  if(this.trie === null) {
    this.trie = new Trie(word);
  }
  var traverse = function(trie){
    if(word < trie.str) {
      if(trie.left === null){
        trie.left = new Trie(word)
        return;
      }
      else {
        this.traverse(trie.left);
      }
    }
    else {
      //word >= trie.str
      if(trie.right === null) {
        trie.right = new Trie(word);
        return;
      }
      else {
        this.traverse(trie.right);
      }
    }
  }
  traverse(this.trie);
};

/**
 * Returns if the word is in the trie.
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
  var isFound = false;
  var traverse = function(trie) {
    if(trie.str === word){
      isFound = true;
      return isFound;
    }
    else if(word < trie.str){
      traverse(trie.left);
    }
    else {
      traverse(trie.right);
    }
  }
  return traverse(this.trie);
};

/**
 * Returns if there is any word in the trie that starts with the given prefix.
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
  /*'string'.includes('sea',0);*/
  var isFound = false;
  var traverse = function(trie) {
    if(trie.str.includes(prefix,0)){
      isFound = true;
      return isFound;
    }
    else if(word < trie.str){
      traverse(trie.left);
    }
    else {
      traverse(trie.right);
    }
  }
  return traverse(this.trie);
};

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */