Implement the Trie Data Structure

Suppose you're asked during an interview to design an autocompletion system. On the client side, you have an input box. When users start typing things into the input, it should parse what's been typed and make suggestions based on that.

For example, if the user has typed "cat", we may fetch "cat", "category", and "catnip" as recommendations to display. This seems pretty simple-- we could just do a scan of all the words that start with "cat" and retrieve them. You can do this by storing the words in an array and doing a binary search in O(log n) time complexity, with n being the number of words to search through.

But what if you have millions of words to retrieve and wanted to separate the search time from vocabulary size?

A trie (for data reTRIEval), or prefix tree, would be what you want. Let's implement one today.

We should implement: - An add method that can add words to the trie - A search method that returns the depth of a word - A remove method that removes the word

Constraints

• Total number of characters (not total number of strings) to be inserted <= 100000
• The characters will only comprise of lowercase alphabets
• Expected time complexity for add, search and delete : O(n) n being the length of the word
• Expected space complexity : O(26 * n * N) where N is number of strings

```js
class Trie {
  // fill this class out
	add(val) {}

	search(val) {}

	remove(val) {}
}

// const trie = new Trie();
// console.log(trie.add('cherry'));
// console.log(trie);
// console.log(trie.search('cherry'));
```

```java
class Trie {
    // fill this class out
    void add(String val) {}

    boolean search(String val) {
        return false;
    }

    void remove(String val) {}
}

// Trie trie = new Trie();
// System.out.println(trie.add("cherry"));
// System.out.println(trie);
// System.out.println(trie.search("cherry"));
```
```python
class Trie:
    # fill this class out
    def add(self, val):
        pass

    def search(self, val):
        pass

    def remove(self, val):
        pass

# trie = Trie()
# print(trie.add('cherry'))
# print(trie)
# print(trie.search('cherry'))
```
```cpp
#include <string>

class Trie {
public:
    // fill this class out
    void add(std::string val) {}

    bool search(std::string val) {
        return false;
    }

    void remove(std::string val) {}
};

// Trie trie;
// std::cout << trie.add("cherry");
// std::cout << trie;
// std::cout << trie.search("cherry");
```
```csharp
public class Trie {
    // fill this class out
    public void Add(string val) {}

    public bool Search(string val) {
        return false;
    }

    public void Remove(string val) {}
}

// Trie trie = new Trie();
// Console.WriteLine(trie.Add("cherry"));
// Console.WriteLine(trie);
// Console.WriteLine(trie.Search("cherry"));
```
```go
type Trie struct {
}

// fill this struct out
func (t *Trie) Add(val string) {}

func (t *Trie) Search(val string) bool {
	return false
}

func (t *Trie) Remove(val string) {}

// trie := Trie{}
// fmt.Println(trie.Add("cherry"))
// fmt.Println(trie)
// fmt.Println(trie.Search("cherry"))
```

To implement a trie, we'll need to know the basics of how one works.

The easiest way is to imagine a tree in this shape:

          *
         / \ 
        c   a
       / \   \
      a   o   end
     / \   \
    t   r   w
   /     \   \
  end    end  end

Observing the above, you'll note that each path from the root to a leaf constitutes a string. Most nodes, except for the last, have a character value (except for the leaves which indicate the end, letting us know it's a word). So what we'd want to do in the following methods is:

add - create nodes and place them in the right place

search - traverse through nodes until you find possible words

remove - delete all associated nodes

Let's start by defining the class constructor. We'll start with just the head node, which will have a val property of an empty string (since it's only the root and can branch off to any letter), and an empty children object which we'll populate with add.

```js
class Trie {
	constructor() {
		this.head = {
			val: '',
			children: {}
		};
	}
}
```
```py
class TrieNode:
    # Trie node class
    def __init__(self):
        self.children = [None] * 26
        # isEndOfWord is True
        # if node represent the end of word
        self.isEndOfWord = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
```
```java
public class Trie {

    private TrieNode root;

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

class TrieNode {
 
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord;

    TrieNode(){
        isEndOfWord = false;
        for (int i = 0; i < 26; i++)
            children[i] = null;
    }
}
```
```csharp
public class TrieNode
{
    public TrieNode[] Children = new TrieNode[26];
    public bool IsEndOfWord;

    public TrieNode()
    {
        IsEndOfWord = false;
        for (int i = 0; i < 26; i++)
            Children[i] = null;
    }

}

public class Trie
{
    private readonly TrieNode _root;

    public Trie()
    {
        _root = new TrieNode();
    }
}
```
```cpp
class TrieNode {
public:
    TrieNode* children[26];
    bool isEndOfWord;

    TrieNode() {
        this->isEndOfWord = false;

        for (int i = 0; i < 26; i++)
            this->children[i] = NULL;
    }
};

class Trie {
private:
    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }
};
```
```go
type TrieNode struct {
	children [26]*TrieNode
	isEndOfWord bool
}

type Trie struct {
	root *TrieNode
}

func NewTrieNode() *TrieNode {
	node := &TrieNode{}
	node.isEndOfWord = false
	for i:=0; i<26; i++ {
		node.children[i] = nil
	}
	return node
}

func NewTrie() *Trie {
	trie := &Trie{}
	trie.root = NewTrieNode()
	return trie
}
```

Next up, let's implement add.

A word is passed into the method (let's say "cat"), and begins to get processed. We'll first want to have references to the head node so that we can include each letter in cat as its eventual children and grandchildren. Here's how we accomplish establishing this lineage:

let currentNode = this.head,
  newNode = null,
  currentChar = val.slice(0, 1);

// val is used to keep track of the remaining letters
val = val.slice(1);

# add key into trie if not present
# else just marks the leaf node
pCrawl = self.root
length = len(key)
for level in range(length):
    index = self._charToIndex(key[level])

Node currentNode = this.head;
Node newNode = null;
String currentChar = val.substring(0, 1);

// val is used to keep track of the remaining letters
val = val.substring(1);

Node* currentNode = this->head;
Node* newNode = nullptr;
string currentChar = val.substr(0,1);

// val is used to keep track of the remaining letters
val = val.substr(1);

Node currentNode = this.head;
Node newNode = null;
string currentChar = val.Substring(0, 1);

// val is used to keep track of the remaining letters
val = val.Substring(1);

currentNode := this.head
var newNode *Node = nil
currentChar := val[0:1]

// val is used to keep track of the remaining letters
val = val[1:]

We can use a while loop to determine the appropriate place to assign our word as a child key in a children hash. It does this by trying to look for each of our word's characters in the current node's children hash, and if there's a match, we try to place it in the next child's children hash. This handles the case where lineages like c -> a -> t in "category" may have already been previously added with a word like "cater".

add(val) {
  let currentNode = this.head,
    newNode = null,
    currentChar = val.slice(0, 1);

  val = val.slice(1);

  // See how deep we can get in any existing branches
  while (
    typeof currentNode.children[currentChar] !== 'undefined' &&
    currentChar.length > 0
  ) {
    currentNode = currentNode.children[currentChar];
    currentChar = val.slice(0, 1);
    val = val.slice(1);
  }
}

def add(self, key):
    # add key into trie if not present
    # else just marks the leaf node
    pCrawl = self.root
    length = len(key)
    for level in range(length):
        index = self._charToIndex(key[level])

void add(String val) {
  Node currentNode = this.head;
  Node newNode = null;
  String currentChar = val.substring(0, 1);
  val = val.substring(1);

  // See how deep we can get in any existing branches
  while (
    currentNode.children.get(currentChar) != null &&
    currentChar.length() > 0
  ) {
    currentNode = currentNode.children.get(currentChar);
    currentChar = val.substring(0, 1);
    val = val.substring(1);
  }
}

void add(string val) {
  Node* currentNode = this->head;
  Node* newNode = nullptr;
  string currentChar = val.substr(0, 1);
  val = val.substr(1);

  // See how deep we can get in any existing branches
  while (
    currentNode->children[currentChar] != NULL &&
    currentChar.size() > 0
  ) {
    currentNode = currentNode->children[currentChar];
    currentChar = val.substr(0, 1);
    val = val.substr(1);
  }
}

void Add(string val) {
  Node currentNode = this.head;
  Node newNode = null;
  string currentChar = val.Substring(0, 1);
  val = val.Substring(1);

  // See how deep we can get in any existing branches
  while (
    currentNode.children.ContainsKey(currentChar) &&
    currentChar.Length > 0
  ) {
    currentNode = currentNode.children[currentChar];
    currentChar = val.Substring(0, 1);
    val = val.Substring(1);
  }
}

func (t *Trie) Add(val string) {
  currentNode := t.head
  var newNode *Node
  currentChar := string(val[0])
  val = val[1:]

  // See how deep we can get in any existing branches
  for _, ok := currentNode.children[currentChar]; ok && len(currentChar) > 0; _, ok = currentNode.children[currentChar] {
    currentNode = currentNode.children[currentChar]
    currentChar = string(val[0])
    val = val[1:]
  }
}

Let's pause to ensure we've properly understood what's going on.

The prior code handled when there were children already registered. It doesn't make sense to add a new branch of c -> a if we encounter c -> a -> t, c -> a -> b, etc. So if we already have:

  c
 /
a

and we're trying to add cat, we just add a new node for t at the end.

Next we'll use a while loop to iterate through each letter of the word, and create nodes for each of the children and attach them to the appropriate key. Depending on the language, there may be a more efficient implementation where the lookup and initialization happen simultaneously.

add(val) {
  let currentNode = this.head,
    newNode = null,
    currentChar = val.slice(0, 1);

  val = val.slice(1);

  // See how deep we can get in any existing branches
  while (
    typeof currentNode.children[currentChar] !== 'undefined' &&
    currentChar.length > 0
  ) {
    currentNode = currentNode.children[currentChar];
    currentChar = val.slice(0, 1);
    val = val.slice(1);
  }

  // Break each character into levels respectively
  // 'val' is the character, and 'value' lets us know if it terminates
  while (currentChar.length) {
    newNode = {
      val: currentChar,
      value: val.length === 0 ? null : undefined,
      children: {},
    };

    currentNode.children[currentChar] = newNode;

    currentNode = newNode;

    currentChar = val.slice(0, 1);
    val = val.slice(1);
  }
}

def add(self, key):
  # add key into trie if not present
  # else just marks the leaf node
  pCrawl = self.root
  length = len(key)
  for level in range(length):
      index = self._charToIndex(key[level])
      if not pCrawl.children[index]:
          pCrawl.children[index] = TrieNode()
      pCrawl = pCrawl.children[index]

      # mark last node as leaf
  pCrawl.isEndOfWord = True

void add(String val) {
    TrieNode currentNode = this.getRoot();
    TrieNode newNode;
    String currentChar = val.substring(0, 1);
    val = val.substring(1);

    // See how deep we can get in any existing branches
    while (
            currentNode.getChildren().containsKey(currentChar) &&
            currentChar.length() > 0
    ) {
        currentNode = currentNode.getChildren().get(currentChar);
        currentChar = val.substring(0, 1);
        val = val.substring(1);
    }

    // Break each character into levels respectively
    // 'val' is the character, and 'value' lets us know if it terminates
    while (currentChar.length() != 0) {
        newNode = new TrieNode();
        newNode.setVal(currentChar);
        newNode.setValue(val.length() == 0 ? null : undefined);
        newNode.setChildren(new HashMap<>());

        currentNode.getChildren().put(currentChar, newNode);
        currentNode = newNode;
        currentChar = val.substring(0, 1);
        val = val.substring(1);
    }
}

void add(string val) {
  TrieNode* currentNode = this->getRoot();
  TrieNode* newNode = nullptr;
  string currentChar = val.substr(0, 1);
  val = val.substr(1);

  // See how deep we can get in any existing branches
  while (
    currentNode->getChildren()[currentChar] != nullptr && 
    !currentChar.empty()
  ) {
    currentNode = currentNode->getChildren()[currentChar];
    currentChar = val.substr(0, 1);
    val = val.substr(1);
  }

  // Split each character into levels respectively
  // 'val' is the character, and 'value' lets us know if it terminates
  while (!currentChar.empty()) {
    newNode = new TrieNode();
    newNode->setVal(currentChar);
    newNode->setValue(val.empty() ? nullptr : undefined);
    newNode->setChildren({});

    currentNode->getChildren()[currentChar] = newNode;
    currentNode = newNode;
    currentChar = val.substr(0, 1);
    val = val.substr(1);
  }
}

void Add(string val)
{
    TrieNode currentNode = this.Root;
    TrieNode newNode;
    string currentChar = val.Substring(0, 1);
    val = val.Substring(1);

    // See how deep we can get in any existing branches
    while (
        currentNode.Children.ContainsKey(currentChar) &&
        currentChar.Length > 0
    ) {
        currentNode = currentNode.Children[currentChar];
        currentChar = val.Substring(0, 1);
        val = val.Substring(1);
    }

    // Break each character into levels respectively
    // 'val' is the character, and 'value' lets us know if it terminates
    while (currentChar.Length != 0) {
        newNode = new TrieNode();
        newNode.Val = currentChar;
        newNode.Value = val.Length == 0 ? null : String.Empty;
        newNode.Children = new Dictionary<string, TrieNode>();

        currentNode.Children[currentChar] = newNode;
        currentNode = newNode;
        currentChar = val.Substring(0, 1);
        val = val.Substring(1);
    }
}

func (t *trie) add(val string) {
    currentNode := t.root
    var newNode *node
    currentChar := val[0:1]
    val = val[1:]

    // See how deep we can get in any existing branches
    for currentNode.children[currentChar] != nil && len(currentChar) > 0 {
        currentNode = currentNode.children[currentChar]
        currentChar = val[0:1]
        val = val[1:]
    }

    // Split each character into levels respectively
    // 'val' is the character, and 'value' lets us know if it terminates
    for len(currentChar) != 0 {
        newNode = &node{
            val: currentChar,
            children: make(map[string]*node),
        }

        if len(val) == 0 {
            newNode.value = nil
        }

        currentNode.children[currentChar] = newNode

        currentNode = newNode
        currentChar = val[0:1]
        val = val[1:]
    }
}

We can move onto the search method!

This is similarly straightforward. The key part is again testing our currentChar/current character against the children hash's keys. If our current character is a child of the current node, then we can traverse to that child and see if the next letter matches as well.

Note that in our example, we're keeping track of depth and returning it. You can do this, or return the actual word itself once you hit the end of a word.

```js
class Trie {
  constructor() {
    this.head = {
      val: '',
      children: {},
    };
  }

  add(val) {
    let currentNode = this.head,
      newNode = null,
      currentChar = val.slice(0, 1);

    val = val.slice(1);

    // See how deep we can get in any existing branches
    while (
      typeof currentNode.children[currentChar] !== 'undefined' &&
      currentChar.length > 0
    ) {
      currentNode = currentNode.children[currentChar];
      currentChar = val.slice(0, 1);
      val = val.slice(1);
    }

    // Break each character into levels respectively
    // 'val' is the character, and 'value' lets us know if it terminates
    while (currentChar.length) {
      newNode = {
        val: currentChar,
        value: val.length === 0 ? null : undefined,
        children: {},
      };

      currentNode.children[currentChar] = newNode;

      currentNode = newNode;

      currentChar = val.slice(0, 1);
      val = val.slice(1);
    }
  }

  search(val) {
    let currentNode = this.head,
      currentChar = val.slice(0, 1),
      depth = 0;

    val = val.slice(1);

    while (
      typeof currentNode.children[currentChar] !== 'undefined' &&
      currentChar.length > 0
    ) {
      currentNode = currentNode.children[currentChar];
      currentChar = val.slice(0, 1);
      val = val.slice(1);
      depth += 1;
    }

    if (currentNode.value === null && val.length === 0) {
      return depth;
    } else {
      return -1;
    }
  }
}
```
```py
class TrieNode:
    # Trie node class
    def __init__(self):
        self.children = [None] * 26
        # isEndOfWord is True
        # if node represent the end of word
        self.isEndOfWord = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def _charToIndex(self, ch):
        # converts the character into index
        return ord(ch) - ord("a")

    def add(self, key):
        # add key into trie if not present
        # else just marks the leaf node
        pCrawl = self.root
        length = len(key)
        for level in range(length):
            index = self._charToIndex(key[level])
            if not pCrawl.children[index]:
                pCrawl.children[index] = TrieNode()
            pCrawl = pCrawl.children[index]

            # mark last node as leaf
        pCrawl.isEndOfWord = True

    def search(self, key):
        # search key in trie, return True if present else return False
        pCrawl = self.root
        length = len(key)
        for level in range(length):
            index = self._charToIndex(key[level])
            if not pCrawl.children[index]:
                return False
            pCrawl = pCrawl.children[index]
        return pCrawl != None and pCrawl.isEndOfWord
```
```java
class TrieNode {
    TrieNode[] children;
    boolean isEndOfWord;

    public TrieNode() {
        this.children = new TrieNode[26];
        this.isEndOfWord = false;
    }
}

class Trie {
    private TrieNode root;

    public Trie() {
        this.root = new TrieNode();
    }

    private int charToIndex(char ch) {
        return ch - 'a';
    }

    public void add(String key) {
        TrieNode pCrawl = root;
        int length = key.length();
        for(int level = 0; level < length; level++) {
            int index = charToIndex(key.charAt(level));
            if(pCrawl.children[index] == null)
                pCrawl.children[index] = new TrieNode();
            pCrawl = pCrawl.children[index];
        }
        pCrawl.isEndOfWord = true;
    }

    public boolean search(String key) {
        TrieNode pCrawl = root;
        int length = key.length();
        for(int level = 0; level < length; level++) {
            int index = charToIndex(key.charAt(level));
            if(pCrawl.children[index] == null)
                return false;
            pCrawl = pCrawl.children[index];
        }
        return (pCrawl != null && pCrawl.isEndOfWord);
    }
}
```
```csharp
public class TrieNode
{
    public TrieNode[] children = new TrieNode[26];
    public bool isEndOfWord = false;
}

public class Trie
{
    private TrieNode root;

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

    private int CharToIndex(char ch) 
    {
        return ch - 'a';
    }

    public void Add(string key)
    {
        int length = key.Length;
        TrieNode pCrawl = root;

        for (int level = 0; level < length; level++)
        {
            int index = CharToIndex(key[level]);
            if (pCrawl.children[index] == null)
                pCrawl.children[index] = new TrieNode();

            pCrawl = pCrawl.children[index];
        }
        pCrawl.isEndOfWord = true;
    }

    public bool Search(string key)
    {
        int length = key.Length;
        TrieNode pCrawl = root;

        for (int level = 0; level < length; level++)
        {
            int index = CharToIndex(key[level]);

            if (pCrawl.children[index] == null)
                return false;

            pCrawl = pCrawl.children[index];
        }
        return (pCrawl != null && pCrawl.isEndOfWord);
    }
}
```
```cpp
#include <bits/stdc++.h>
using namespace std;

const int ALPHABET_SIZE = 26;

struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    bool isEndOfWord;
};

struct TrieNode* getNode() {
    struct TrieNode* pNode = new TrieNode;
    pNode->isEndOfWord = false;

    for(int i = 0; i < ALPHABET_SIZE; i++)
        pNode->children[i] = nullptr;

    return pNode;
}

void add(struct TrieNode* root, string key) {
    struct TrieNode* pCrawl = root;

    for(int i = 0; i < key.length(); i++) {
        int index = key[i] - 'a';
        if(!pCrawl->children[index])
            pCrawl->children[index] = getNode();

        pCrawl = pCrawl->children[index];
    }
    pCrawl->isEndOfWord = true;
}

bool search(struct TrieNode* root, string key) {
    struct TrieNode* pCrawl = root;

    for(int i = 0; i < key.length(); i++) {
        int index = key[i] - 'a';
        if(!pCrawl->children[index])
            return false;
        pCrawl = pCrawl->children[index];
    }
    return (pCrawl != nullptr && pCrawl->isEndOfWord);
}
```
```go
package main

import (
  "fmt"
)

type TrieNode struct {
  Children [26]*TrieNode
  IsEndOfWord bool
}

type Trie struct {
  Root *TrieNode
}

func NewTrieNode() *TrieNode {
  node := &TrieNode{}
  for i := range node.Children {
    node.Children[i] = nil
  }
  node.IsEndOfWord = false
  return node
}

func CharToIndex(ch byte) int {
  return int(ch - 'a')
}

func (t *Trie) Add(key string) {
  pCrawl := t.Root
  length := len(key)

  for level := 0; level < length; level++ {
    index := CharToIndex(key[level])
    if pCrawl.Children[index] == nil {
      pCrawl.Children[index] = NewTrieNode()
    }
    pCrawl = pCrawl.Children[index]
  }
  pCrawl.IsEndOfWord = true
}

func (t* Trie) Search(key string) bool {
  pCrawl := t.Root
  length := len(key)

  for level := 0; level < length; level++ {
    index := CharToIndex(key[level])
    if pCrawl.Children[index] == nil {
      return false
    }
    pCrawl = pCrawl.Children[index]
  }
  return pCrawl != nil && pCrawl.IsEndOfWord
}
```

We can search the trie in O(n) time with n being the length of the word.

Finally, we can implement remove.

To know whether we should remove something, we should first check if the word is in the trie. So first, we'll need to do a search for it and see if we get a depth value returned.

remove(val) {
  let depth = this.search(val);
  if (depth) {
    removeHelper(this.head, val, depth);
  }
}

def remove(self, root, key, depth=0):
  pCrawl = self.root

  if not pCrawl:
      return None

      # if last character of key is being processed
  if depth == len(key):
      # this node is no more end of word after removal of given key
      if pCrawl.isEndOfWord:
          pCrawl.isEndOfWord = False
      # If key given is not prefix of any other word
      if self._empty(pCrawl):
          pCrawl = None
      return pCrawl

void remove(String val) {
    int depth = this.search(val);
    if(depth != 0) {
        removeHelper(this.head, val, depth);
    }
}

TrieNode remove(TrieNode root, String key, int depth) {
    TrieNode pCrawl = root;

    if (pCrawl == null)
        return null;

    if (depth == key.length()) {
        if (pCrawl.isEndOfWord)
            pCrawl.isEndOfWord = false;

        if (isEmpty(pCrawl))
            pCrawl = null;

        return pCrawl;
    }
}

public void Remove(string val) {
    int depth = this.Search(val);
    if (depth != 0) {
        RemoveHelper(this.head, val, depth);
    }
}

public TrieNode Remove(TrieNode root, string key, int depth = 0) {
    TrieNode pCrawl = root;

    if (pCrawl == null)
        return null;

    if (depth == key.Length) {
        if (pCrawl.IsEndOfWord)
            pCrawl.IsEndOfWord = false;

        if (IsEmpty(pCrawl))
            pCrawl = null;

        return pCrawl;
    }
}

void remove(std::string val) {
    int depth = this->search(val);
    if (depth) {
        removeHelper(this->head, val, depth);
    }
}

TrieNode* remove(TrieNode* root, std::string key, int depth = 0) {
    TrieNode* pCrawl = root;

    if (!pCrawl)
        return nullptr;

    if (depth == key.size()) {
        if (pCrawl->isEndOfWord)
            pCrawl->isEndOfWord = false;

        if (isEmpty(pCrawl))
            pCrawl = nullptr;

        return pCrawl;
    }
}

func (t *Trie) remove(val string) {
    depth := t.search(val)
    if depth != 0 {
        t.removeHelper(t.head, val, depth)
    }
}

func (t *Trie) remove(root *TrieNode, key string, depth int) *TrieNode {
    pCrawl := root

    if pCrawl == nil {
        return nil
    }

    if depth == len(key) {
        if pCrawl.isEndOfWord {
            pCrawl.isEndOfWord = false
        }
        if empty(pCrawl) {
            pCrawl = nil
        }
        return pCrawl
    }
    return nil
}

If so, we can recursively call a removeHelper method to recursively delete child nodes if found.

```js
function removeHelper(node, val, depth) {
	if (depth === 0 && Object.keys(node.children).length === 0) {
		return true;
	}

	let currentChar = val.slice(0, 1);

	if (removeHelper(node.children[currentChar], val.slice(1), depth - 1)) {
		delete node.children[currentChar];
		if (Object.keys(node.children).length === 0) {
			return true;
		} else {
			return false;
		}
	} else {
		return false;
	}
}
```
```py
def remove(self, root, key, depth=0):
    pCrawl = self.root

    if not pCrawl:
        return None

        # if last character of key is being processed
    if depth == len(key):
        # this node is no more end of word after removal of given key
        if pCrawl.isEndOfWord:
            pCrawl.isEndOfWord = False
        # If key given is not prefix of any other word
        if self._empty(pCrawl):
            pCrawl = None
        return pCrawl

    # If not last character, recur for the child
    index = self._charToIndex(key[depth])
    pCrawl.children[index] = self.remove(pCrawl.children[index], key, depth + 1)

    # If root does not have any child (its only child got deleted), and it is not end of another word
    if self._empty(pCrawl) and pCrawl.isEndOfWord == False:
        pCrawl = None
    return pCrawl
```
```java
void removeHelper(Node node, String val, int depth) {
    if (depth == 0 && node.getChildren().isEmpty()) {
        return true;
    }

    String currentChar = val.substring(0, 1);

    if (removeHelper(node.getChildren().get(currentChar), val.substring(1), depth - 1)) {
        node.getChildren().remove(currentChar);
        if (node.getChildren().isEmpty()) {
            return true;
        } else {
            return false;
        }
    } else {
        return false;
    }
}
```
```cpp
bool removeHelper(Node *node, std::string val, int depth) {
    if (depth == 0 && node->children.empty()) {
        return true;
    }

    std::string currentChar = val.substr(0, 1);

    if (removeHelper(node->children[currentChar], val.substr(1), depth - 1)) {
        node->children.erase(currentChar);
        if (node->children.empty()) {
            return true;
        } else {
            return false;
        }
    } else {
        return false;
    }
}
```
```csharp
bool RemoveHelper(Node node, string val, int depth)
{
    if (depth == 0 && !node.Children.Any())
    {
        return true;
    }

    string currentChar = val.Substring(0, 1);

    if (RemoveHelper(node.Children[currentChar], val.Substring(1), depth - 1))
    {
        node.Children.Remove(currentChar);
        if (!node.Children.Any())
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    else
    {
        return false;
    }
}
```
```go
func removeHelper(node *Node, val string, depth int) bool {
    if depth == 0 && len(node.children) == 0 {
        return true
    }

    currentChar := string(val[0])

    if removeHelper(node.children[currentChar], val[1:], depth - 1) {
        delete(node.children,currentChar)
        if len(node.children) == 0 {
           return true
        } else {
           return false
        }
    } else {
        return false
    }
}
```

One Pager Cheat Sheet

• You should implement a Trie data structure with add, search, and remove methods that have O(n) time complexity & O(26 * n * N) space complexity, where n is the length of the word and N is the total number of strings.
• We need to be familiar with Tries, which can be represented by a tree structure like * / \ c a / \ o end / \ t r / \ end end end.
• Using add, search and remove, we can construct and utilize a class structure to create and traverse a tree structure, with a head node that branches off to each character value, and leaves to indicate the end of a word.
• Create references to the head node, then process each letter of the word (e.g. "cat") and add them as children or grandchildren, either adding a new key or marking the existing leaf node, depending on if the key is present or not.
• We can use a while loop to determine the appropriate place to assign our word as a child key in a children hash, searching for each of its characters and handling the lineages created by previously added words.
• Let's pause to ensure we've properly understood the situation, to avoid adding a new branch of c -> a when we already have c -> a -> t, c -> a -> b, etc.
• We can use a while loop to iterate through each letter of the word and create nodes and attach them to the appropriate key in both JS and Python.
• We can traverse from node to node to search for words by comparing our currentChar to the children's keys, and optionally returning the depth or the word itself once the end of the word is reached.
• We can search and remove words from the trie in O(n) time using removeHelper and _empty functions.
• We can recursively call a removeHelper method to delete any child nodes found.