1var assert = require('assert');
2
3class Trie {
4  constructor() {
5    this.head = {
6      val: '',
7      children: {},
8    };
9  }
10
11  add(val) {
12    let currentNode = this.head,
13      newNode = null,
14      currentChar = val.slice(0, 1);
15
16    val = val.slice(1);
17
18    // See how deep we can get in any existing branches
19    while (
20      typeof currentNode.children[currentChar] !== 'undefined' &&
21      currentChar.length > 0
22    ) {
23      currentNode = currentNode.children[currentChar];
24      currentChar = val.slice(0, 1);
25      val = val.slice(1);
26    }
27
28    // Break each character into levels respectively
29    // 'val' is the character, and 'value' lets us know if it terminates
30    while (currentChar.length) {
31      newNode = {
32        val: currentChar,
33        value: val.length === 0 ? null : undefined,
34        children: {},
35      };
36
37      currentNode.children[currentChar] = newNode;
38
39      currentNode = newNode;
40
41      currentChar = val.slice(0, 1);
42      val = val.slice(1);
43    }
44  }
45
46  search(val) {
47    let currentNode = this.head,
48      currentChar = val.slice(0, 1),
49      depth = 0;
50
51    val = val.slice(1);
52
53    while (
54      typeof currentNode.children[currentChar] !== 'undefined' &&
55      currentChar.length > 0
56    ) {
57      currentNode = currentNode.children[currentChar];
58      currentChar = val.slice(0, 1);
59      val = val.slice(1);
60      depth += 1;
61    }
62
63    if (currentNode.value === null && val.length === 0) {
64      return depth;
65    } else {
66      return -1;
67    }
68  }
69
70  remove(val) {
71    function removeHelper(node, val, depth) {
72      if (depth === 0 && Object.keys(node.children).length === 0) {
73        return true;
74      }
75
76      let currentChar = val.slice(0, 1);
77
78      if (removeHelper(node.children[currentChar], val.slice(1), depth - 1)) {
79        delete node.children[currentChar];
80        if (Object.keys(node.children).length === 0) {
81          return true;
82        } else {
83          return false;
84        }
85      } else {
86        return false;
87      }
88    }
89
90    let depth = this.search(val);
91    if (depth) {
92      removeHelper(this.head, val, depth);
93    }
94  }
95}
96
97function Node(val) {
98  this.val = val;
99  this.left = null;
100  this.right = null;
101}
102
103// Regular binary trees
104var tree1 = new Node(4);
105tree1.left = new Node(1);
106tree1.right = new Node(3);
107
108var tree2 = new Node(5);
109tree2.left = new Node(10);
110tree2.left.left = new Node(17);
111tree2.left.right = new Node(3);
112tree2.right = new Node(8);
113
114// Binary search trees
115var tree3 = new Node(6);
116tree3.left = new Node(3);
117
118var tree4 = new Node(5);
119tree4.left = new Node(3);
120tree4.left.left = new Node(2);
121tree4.left.left.left = new Node(1);
122
123var tree5 = new Node(8);
124tree5.left = new Node(6);
125tree5.right = new Node(9);
126tree5.left.left = new Node(5);
127tree5.left.right = new Node(7);
128tree5.right.right = new Node(10);
129
130try {
131  var newTrie = new Trie();
132  newTrie.add('cherry');
133  assert.equal(newTrie.search('cherry'), 6);
134
135  console.log(
136    'PASSED: ' + 'Can instantiate a trie, add `cherry`, and get a depth of `6`'
137  );
138} catch (err) {
139  console.log(err);
140}
141
142try {
143  newTrie.remove('cherry');
144  assert.equal(newTrie.search('cherry'), -1);
145
146  console.log('PASSED: ' + 'Can remove `cherry` from the trie');
147} catch (err) {
148  console.log(err);
149}