Trie

Space	Time
	Access	Lookup	Insertion	Deletion
O(n)	N/A	O(n)	O(n)	O(n)

Definition

Short

Trie is a tree-like data structure used to store and efficiently retrieve strings.

Simplified

Trie as a kind of magical tree. But instead of having fruits or leaves, this tree has letters on each branch. Now, suppose you want to find a word. You start at the root of the tree and follow the branches that have the letters of your word in order. If you can reach the end of your word by following the branches, voila, the word is in the tree!

For example, if you're looking for the word "cat", you'd start at the root, find a branch with the letter 'c', then from there find a branch with 'a', and finally a branch with 't'. If all these branches exist in the correct order, the word "cat" is in your tree.

This magical tree is super efficient and can help you find words really quickly, even if you have a dictionary's worth of words in your tree. That's why it's used in software engineering, especially in tasks like word suggestions and spell checks. It's like having a super-powered dictionary.

Detailed

Trie, also known as a digital or prefix tree, is a search tree used in computer science. It's an ordered tree data structure for storing dynamic sets or associative arrays where keys are typically strings. Unlike binary search trees, the key isn't stored in the node, but is defined by the node's position in the tree. All descendants of a node share a common prefix of the string associated with that node, with the root associated with an empty string. Values are usually associated with leaves and some inner nodes that correspond to keys of interest. A compact prefix tree is a space-optimized version of a trie.

Practice

Practice

Aspect	Pseudo Code
Insertion	add_word(word) current_node = root for char in word: current_node = current_node.children[char] ?: TrieNode() current_node.is_end_of_word = True
Deletion Recursive	delete_word(word) delete_word(root, word, 0) delete_word(current_node, word, index) if current_node == ø: return False if index == word.length: if !current_node.is_end_of_word: return False current_node.is_end_of_word = false return current_node.children == ø char = word[index] next_node = current_node.children[char] ?: return false should_delete_current_node = delete_word(next_node, word, index + 1) if should_delete_current_node: current_node.children.remove(char) return current_node.children == ø
Deletion Iterative	delete_word_iterative(word) current_node = root index = 0 nodes_stack = Stack<Pair<TrieNode, Int>>() while index < word.length: char = word[index] next_node = current_node.children[char] if next_node == ø: return nodes_stack.add(Pair(current_node, index)) current_node = next_node index++ current_node.is_end_of_word = false while nodes_stack != ø: parentNode, parentIndex = nodes_stack.pop() if current_node.children == ø and not current_node.is_end_of_word: parentNode.children.remove(word[parentIndex]) current_node = parentNode
Suggest Next Characters Recursive	suggest_next_characters(prefix) lastNode = get_last_character_node(prefix) suggestions = List<Char>() if lastNode != ø: suggest_next_characters(lastNode, prefix, suggestions) return suggestions suggest_next_characters(node, currentPrefix, suggestions) if node.is_end_of_word: suggestions.add(currentPrefix[currentPrefix.length - 1]) for char, child_node in node.children: suggest_next_characters(child_node, currentPrefix + char, suggestions)
Suggest Next Characters Iterative	suggest_next_characters_iterative(prefix) suggestions = List<Char>() current_node = root currentPrefix = "" for char in prefix: current_node = current_node.children[char] ?: return suggestions currentPrefix += char stack = Stack<Pair<TrieNode, String>>() stack.add(Pair(current_node, currentPrefix)) while stack != ø: node, current = stack.pop() if node.is_end_of_word: suggestions.add(current.last()) for char, child_node in node.children: stack.add(Pair(child_node, current + char)) return suggestions
Search	does_word_exist(word) lastNode = get_last_character_node(word) return lastNode?.is_end_of_word ?: false
Starts with	starts_with(prefix) return get_last_character_node(prefix) != ø get_last_character_node(prefix) current_node = root for char in prefix: current_node = current_node.children[char] ?: return ø return current_node

Solution

package main

type TrieNode struct {
	children     map[rune]*TrieNode
	isEndOfWord  bool
}

type Trie struct {
	root *TrieNode
}

func NewTrie() *Trie {
	return &Trie{
		root: &TrieNode{
			children: make(map[rune]*TrieNode),
		},
	}
}

func (t *Trie) addWord(word string) {
	currentNode := t.root
	for _, char := range word {
		if _, exists := currentNode.children[char]; !exists {
			currentNode.children[char] = &TrieNode{
				children: make(map[rune]*TrieNode),
			}
		}
		currentNode = currentNode.children[char]
	}
	currentNode.isEndOfWord = true
}

func (t *Trie) deleteWord(word string) {
	t.depthFirstDelete(t.root, word, 0)
}

func (t *Trie) depthFirstDelete(currentNode *TrieNode, word string, index int) {
	if currentNode == nil {
		return
	}

	if index == len(word) {
		if !currentNode.isEndOfWord {
			return
		}
		currentNode.isEndOfWord = false
		if len(currentNode.children) == 0 {
			delete(currentNode.children, rune(word[index-1]))
		}
		return
	}

	char := rune(word[index])
	nextNode, exists := currentNode.children[char]

	if !exists {
		return
	}

	t.depthFirstDelete(nextNode, word, index+1)

	if len(nextNode.children) == 0 && !nextNode.isEndOfWord {
		delete(currentNode.children, char)
	}
}

func (t *Trie) DeleteWordIterative(word string) {
	currentNode := t.root
	index := 0
	var nodesStack []struct {
		node  *TrieNode
		index int
	}

	for index < len(word) {
		char := rune(word[index])
		nextNode, exists := currentNode.children[char]

		if !exists {
			return
		}

		nodesStack = append(nodesStack, struct {
			node  *TrieNode
			index int
		}{node: currentNode, index: index})

		currentNode = nextNode
		index++
	}

	currentNode.isEndOfWord = false

	for len(nodesStack) > 0 {
		nodeWithIndex := nodesStack[len(nodesStack)-1]
		nodesStack = nodesStack[:len(nodesStack)-1]

		if len(currentNode.children) == 0 && !currentNode.isEndOfWord {
			delete(nodeWithIndex.node.children, rune(word[nodeWithIndex.index-1]))
		}

		currentNode = nodeWithIndex.node
	}
}

func (t *Trie) suggestNextCharacters(prefix string) []rune {
	lastNode := t.getLastCharacterNode(prefix)
	var suggestions []rune

	if lastNode != nil {
		t.suggestNextCharacters(lastNode, []rune(prefix), &suggestions)
	}

	return suggestions
}

func (t *Trie) suggestNextCharactersIterative(prefix string) []rune {
	var suggestions []rune
	currentNode := t.root
	var currentPrefix []rune

	for _, char := range prefix {
		nextNode, exists := currentNode.children[char]
		if !exists {
			return suggestions
		}
		currentNode = nextNode
		currentPrefix = append(currentPrefix, char)
	}

	stack := []struct {
		node    *TrieNode
		current []rune
	}{
		{node: currentNode, current: currentPrefix},
	}

	for len(stack) > 0 {
		nodeWithPrefix := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		if nodeWithPrefix.node.isEndOfWord {
			suggestions = append(suggestions, nodeWithPrefix.current[len(nodeWithPrefix.current)-1])
		}

		for char, childNode := range nodeWithPrefix.node.children {
			stack = append(stack, struct {
				node    *TrieNode
				current []rune
			}{node: childNode, current: append(nodeWithPrefix.current, char)})
		}
	}

	return suggestions
}

func (t *Trie) suggestNextCharacters(node *TrieNode, currentPrefix []rune, suggestions *[]rune) {
	if node.isEndOfWord {
		*suggestions = append(*suggestions, currentPrefix[len(currentPrefix)-1])
	}

	for char, childNode := range node.children {
		t.suggestNextCharacters(childNode, append(currentPrefix, char), suggestions)
	}
}

func (t *Trie) doesWordExist(word string) bool {
	lastNode := t.getLastCharacterNode(word)
	return lastNode != nil && lastNode.isEndOfWord
}

func (t *Trie) getLastCharacterNode(prefix string) *TrieNode {
	currentNode := t.root

	for _, char := range prefix {
		nextNode, exists := currentNode.children[char]
		if !exists {
			return nil
		}
		currentNode = nextNode
	}

	return currentNode
}

func (t *Trie) startsWith(prefix string) bool {
	return t.getLastCharacterNode(prefix) != nil
}

import java.util.*;

public class Trie {

  private TrieNode root;

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

  public void addWord(String word) {
    TrieNode currentNode = root;
    for (char ch : word.toCharArray()) {
      currentNode.children.computeIfAbsent(ch, k -> new TrieNode());
      currentNode = currentNode.children.get(ch);
    }
    currentNode.isEndOfWord = true;
  }

  public void deleteWord(String word) {
    depthFirstDelete(root, word, 0);
  }

  private boolean depthFirstDelete(TrieNode currentNode, String word, int index) {
    if (currentNode == null) {
      return false;
    }

    if (index == word.length()) {
      if (!currentNode.isEndOfWord) {
        return false;
      }
      currentNode.isEndOfWord = false;
      return currentNode.children.isEmpty();
    }

    char ch = word.charAt(index);
    TrieNode nextNode = currentNode.children.get(ch);

    if (nextNode == null) {
      return false;
    }

    boolean shouldDeleteCurrentNode = depthFirstDelete(nextNode, word, index + 1);

    if (shouldDeleteCurrentNode) {
      currentNode.children.remove(ch);
      return currentNode.children.isEmpty();
    }

    return false;
  }

  public void DeleteWordIterative(String word) {
    TrieNode currentNode = root;
    int index = 0;
    Deque<Pair<TrieNode, Integer>> nodesStack = new ArrayDeque<>();

    while (index < word.length()) {
      char ch = word.charAt(index);
      TrieNode nextNode = currentNode.children.get(ch);

      if (nextNode == null) {
        return;
      }

      nodesStack.push(new Pair<>(currentNode, index));
      currentNode = nextNode;
      index++;
    }

    currentNode.isEndOfWord = false;

    while (!nodesStack.isEmpty()) {
      Pair<TrieNode, Integer> nodeWithIndex = nodesStack.pop();
      TrieNode parentNode = nodeWithIndex.getFirst();
      int parentIndex = nodeWithIndex.getSecond();

      if (currentNode.children.isEmpty() && !currentNode.isEndOfWord) {
        Objects.requireNonNull(parentNode).children.remove(word.charAt(parentIndex));
      }

      currentNode = parentNode;
    }
  }

  public List<Character> suggestNextCharacters(String prefix) {
    TrieNode lastNode = getLastCharacterNode(prefix);
    List<Character> suggestions = new ArrayList<>();
    if (lastNode != null) {
      suggestNextCharacters(lastNode, prefix, suggestions);
    }
    return suggestions;
  }

  private void suggestNextCharacters(TrieNode node, String currentPrefix, List<Character> suggestions) {
    if (node.isEndOfWord) {
      suggestions.add(currentPrefix.charAt(currentPrefix.length() - 1));
    }

    for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
      suggestNextCharacters(entry.getValue(), currentPrefix + entry.getKey(), suggestions);
    }
  }

  public List<Character> suggestNextCharactersIterative(String prefix) {
    List<Character> suggestions = new ArrayList<>();
    TrieNode currentNode = root;
    StringBuilder currentPrefix = new StringBuilder();

    for (char ch : prefix.toCharArray()) {
      if (!currentNode.children.containsKey(ch)) {
        return suggestions;
      }
      currentNode = currentNode.children.get(ch);
      currentPrefix.append(ch);
    }

    Deque<Pair<TrieNode, String>> stack = new ArrayDeque<>();
    stack.push(new Pair<>(currentNode, currentPrefix.toString()));

    while (!stack.isEmpty()) {
      Pair<TrieNode, String> nodeWithPrefix = stack.pop();
      TrieNode node = nodeWithPrefix.getFirst();
      String current = nodeWithPrefix.getSecond();

      if (node.isEndOfWord) {
        suggestions.add(current.charAt(current.length() - 1));
      }

      for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
        stack.push(new Pair<>(entry.getValue(), current + entry.getKey()));
      }
    }

    return suggestions;
  }

  public boolean doesWordExist(String word) {
    TrieNode lastNode = getLastCharacterNode(word);
    return lastNode != null && lastNode.isEndOfWord;
  }

  private TrieNode getLastCharacterNode(String prefix) {
    TrieNode currentNode = root;
    for (char ch : prefix.toCharArray()) {
      if (!currentNode.children.containsKey(ch)) {
        return null;
      }
      currentNode = currentNode.children.get(ch);
    }
    return currentNode;
  }

  public boolean startsWith(String prefix) {
    return getLastCharacterNode(prefix) != null;
  }

  static class TrieNode {

    Map<Character, TrieNode> children;
    boolean isEndOfWord;

    TrieNode() {
      this.children = new HashMap<>();
      this.isEndOfWord = false;
    }
  }
}

class Trie {
  constructor() {
    this.root = { children: new Map(), isEndOfWord: false };
  }

  addWord(word) {
    let currentNode = this.root;
    for (const char of word) {
      currentNode = currentNode.children.set(
        char,
        currentNode.children.get(char) || {
          children: new Map(),
          isEndOfWord: false,
        },
      );
    }
    currentNode.isEndOfWord = true;
  }

  deleteWord(word) {
    this.depthFirstDelete(this.root, word, 0);
  }

  depthFirstDelete(currentNode, word, index) {
    if (!currentNode) {
      return false;
    }

    if (index === word.length) {
      if (!currentNode.isEndOfWord) {
        return false;
      }
      currentNode.isEndOfWord = false;
      return currentNode.children.size === 0;
    }

    const char = word[index];
    const nextNode = currentNode.children.get(char);

    if (!nextNode) {
      return false;
    }

    const shouldDeleteCurrentNode = this.depthFirstDelete(
      nextNode,
      word,
      index + 1,
    );

    if (shouldDeleteCurrentNode) {
      currentNode.children.delete(char);
      return currentNode.children.size === 0;
    }

    return false;
  }

  DeleteWordIterative(word) {
    let currentNode = this.root;
    let index = 0;
    const nodesStack = [];

    while (index < word.length) {
      const char = word[index];
      const nextNode = currentNode.children.get(char);

      if (!nextNode) {
        return;
      }

      nodesStack.push([currentNode, index]);
      currentNode = nextNode;
      index++;
    }

    currentNode.isEndOfWord = false;

    while (nodesStack.length > 0) {
      const [parentNode, parentIndex] = nodesStack.pop();

      if (currentNode.children.size === 0 && !currentNode.isEndOfWord) {
        parentNode.children.delete(word[parentIndex]);
      }

      currentNode = parentNode;
    }
  }

  suggestNextCharacters(prefix) {
    const lastNode = this.getLastCharacterNode(prefix);
    const suggestions = [];
    if (lastNode) {
      this.suggestNextCharacters(lastNode, prefix, suggestions);
    }
    return suggestions;
  }

  suggestNextCharactersIterative(prefix) {
    const suggestions = [];
    let currentNode = this.root;
    let currentPrefix = "";

    for (const char of prefix) {
      if (!currentNode.children.has(char)) {
        return suggestions;
      }
      currentNode = currentNode.children.get(char);
      currentPrefix += char;
    }

    const stack = [[currentNode, currentPrefix]];

    while (stack.length > 0) {
      const [node, current] = stack.pop();

      if (node.isEndOfWord) {
        suggestions.push(current.charAt(current.length - 1));
      }

      for (const [char, childNode] of node.children) {
        stack.push([childNode, current + char]);
      }
    }

    return suggestions;
  }

  doesWordExist(word) {
    const lastNode = this.getLastCharacterNode(word);
    return lastNode && lastNode.isEndOfWord;
  }

  getLastCharacterNode(prefix) {
    let currentNode = this.root;
    for (const char of prefix) {
      if (!currentNode.children.has(char)) {
        return null;
      }
      currentNode = currentNode.children.get(char);
    }
    return currentNode;
  }

  startsWith(prefix) {
    return this.getLastCharacterNode(prefix) !== null;
  }
}

import java.lang.StringBuilder

class Trie {
    data class TrieNode(val children = mutableMapOf<Char, TrieNode>(), var isEndOfWord = false)

    private val root = TrieNode()

    fun addWord(word: String) {
        var currentNode = root
        for (char in word) {
            currentNode = currentNode.children.computeIfAbsent(char) { TrieNode() }
        }
        currentNode.isEndOfWord = true
    }

    fun deleteWord(word: String) {
        deleteWord(root, word, 0)
    }

    private fun deleteWord(currentNode: TrieNode?, word: String, index: Int): Boolean {
        if (currentNode == null) {
            return false
        }

        if (index == word.length) {
            if (!currentNode.isEndOfWord) {
                return false
            }
            currentNode.isEndOfWord = false
            return currentNode.children.isEmpty()
        }

        val char = word[index]
        val nextNode = currentNode.children[char] ?: return false

        val shouldDeleteCurrentNode = deleteWord(nextNode, word, index + 1)

        if (shouldDeleteCurrentNode) {
            currentNode.children.remove(char)
            return currentNode.children.isEmpty()
        }

        return false
    }

    fun DeleteWordIterative(word: String) {
        var currentNode = root
        var index = 0
        val nodesStack = mutableListOf<Pair<TrieNode, Int>>()

        while (index < word.length) {
            val char = word[index]
            val nextNode = currentNode.children[char]

            if (nextNode == null) {
                return
            }

            nodesStack.add(Pair(currentNode, index))
            currentNode = nextNode
            index++
        }

        currentNode.isEndOfWord = false

        while (nodesStack.isNotEmpty()) {
            val (parentNode, parentIndex) = nodesStack.removeAt(nodesStack.size - 1)

            if (currentNode.children.isEmpty() && !currentNode.isEndOfWord) {
                parentNode.children.remove(word[parentIndex])
            }

            currentNode = parentNode
        }
    }

    fun depthFirstDelete(word: String) {
        depthFirstDelete(root, word, 0)
    }

    private fun depthFirstDelete(currentNode: TrieNode, word: String, index: Int) {
        if (index == word.length) {
            currentNode.isEndOfWord = false
            return
        }

        val char = word[index]
        val nextNode = currentNode.children[char] ?: return

        depthFirstDelete(nextNode, word, index + 1)

        if (nextNode.children.isEmpty() && !nextNode.isEndOfWord) {
            currentNode.children.remove(char)
        }
    }

    fun DeleteWordIterative(word: String) {
        var currentNode = root
        var index = 0
        val nodesStack = mutableListOf<Pair<TrieNode, Int>>()

        while (index < word.length) {
            val char = word[index]
            val nextNode = currentNode.children[char]

            if (nextNode == null) {
                return
            }

            nodesStack.add(Pair(currentNode, index))
            currentNode = nextNode
            index++
        }

        currentNode.isEndOfWord = false

        while (nodesStack.isNotEmpty()) {
            val (parentNode, parentIndex) = nodesStack.removeAt(nodesStack.size - 1)

            if (currentNode.children.isEmpty() && !currentNode.isEndOfWord) {
                parentNode.children.remove(word[parentIndex])
            }

            currentNode = parentNode
        }
    }

    fun suggestNextCharacters(prefix: String): List<Char> {
        val lastNode = getLastCharacterNode(prefix)
        val suggestions = mutableListOf<Char>()
        if (lastNode != null) {
            suggestNextCharacters(lastNode, prefix, suggestions)
        }
        return suggestions
    }

    private fun suggestNextCharacters(node: TrieNode, currentPrefix: String, suggestions: MutableList<Char>) {
        if (node.isEndOfWord) {
            suggestions.add(currentPrefix.last())
        }

        for ((char, childNode) in node.children) {
            suggestNextCharacters(childNode, currentPrefix + char, suggestions)
        }
    }

    fun suggestNextCharactersIterative(prefix: String): List<Char> {
        val suggestions = mutableListOf<Char>()
        var currentNode = root
        var currentPrefix = StringBuilder()

        for (char in prefix) {
            currentNode = currentNode.children[char] ?: return suggestions
            currentPrefix.append(char)
        }

        val stack = mutableListOf<Pair<TrieNode, String>>()
        stack.add(Pair(currentNode, currentPrefix.toString()))

        while (stack.isNotEmpty()) {
            val (node, current) = stack.removeAt(stack.size - 1)

            if (node.isEndOfWord) {
                suggestions.add(current.last())
            }

            for ((char, childNode) in node.children) {
                stack.add(Pair(childNode, current + char))
            }
        }

        return suggestions
    }

    fun doesWordExist(word: String): Boolean {
        val lastNode = getLastCharacterNode(word)
        return lastNode?.isEndOfWord ?: false
    }

    private fun getLastCharacterNode(prefix: String): TrieNode? {
        var currentNode = root
        for (char in prefix) {
            currentNode = currentNode.children[char] ?: return null
        }
        return currentNode
    }

    fun startsWith(prefix: String): Boolean {
        return getLastCharacterNode(prefix) != null
    }
}

class Trie:
    class TrieNode:
        def __init__(self):
            self.children = {}
            self.is_end_of_word = False

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

    def add_word(self, word):
        current_node = self.root
        for char in word:
            current_node = current_node.children.setdefault(char, self.TrieNode())
        current_node.is_end_of_word = True

    def delete_word(self, word):
        self.depth_first_delete(self.root, word, 0)

    def depth_first_delete(self, current_node, word, index):
        if current_node is None:
            return False

        if index == len(word):
            if not current_node.is_end_of_word:
                return False
            current_node.is_end_of_word = False
            return len(current_node.children) == 0

        char = word[index]
        next_node = current_node.children.get(char)

        if not next_node:
            return False

        should_delete_current_node = self.depth_first_delete(next_node, word, index + 1)

        if should_delete_current_node:
            del current_node.children[char]
            return len(current_node.children) == 0

        return False

    def depth_first_delete_iterative(self, word):
        current_node = self.root
        index = 0
        nodes_stack = []

        while index < len(word):
            char = word[index]
            next_node = current_node.children.get(char)

            if not next_node:
                return

            nodes_stack.append((current_node, index))
            current_node = next_node
            index += 1

        current_node.is_end_of_word = False

        while nodes_stack:
            parent_node, parent_index = nodes_stack.pop()

            if not current_node.children and not current_node.is_end_of_word:
                del parent_node.children[word[parent_index]]

            current_node = parent_node

    def suggest_next_characters(self, prefix):
        last_node = self.get_last_character_node(prefix)
        suggestions = []
        if last_node:
            self.suggest_next_characters_recursive(last_node, prefix, suggestions)
        return suggestions

    def suggest_next_characters_recursive(self, node, current_prefix, suggestions):
        if node.is_end_of_word:
            suggestions.append(current_prefix[-1])

        for char, child_node in node.children.items():
            self.suggest_next_characters_recursive(child_node, current_prefix + char, suggestions)

    def suggest_next_characters_iterative(self, prefix):
        suggestions = []
        current_node = self.root
        current_prefix = ""

        for char in prefix:
            if char not in current_node.children:
                return suggestions
            current_node = current_node.children[char]
            current_prefix += char

        stack = [(current_node, current_prefix)]

        while stack:
            node, current = stack.pop()

            if node.is_end_of_word:
                suggestions.append(current[-1])

            for char, child_node in node.children.items():
                stack.append((child_node, current + char))

        return suggestions

    def does_word_exist(self, word):
        last_node = self.get_last_character_node(word)
        return last_node and last_node.is_end_of_word

    def get_last_character_node(self, prefix):
        current_node = self.root
        for char in prefix:
            if char not in current_node.children:
                return None
            current_node = current_node.children[char]
        return current_node

    def starts_with(self, prefix):
        return self.get_last_character_node(prefix) is not None

use std::collections::HashMap;

struct TrieNode {
    children: HashMap<char, TrieNode>,
    is_end_of_word: bool,
}

impl TrieNode {
    fn new() -> TrieNode {
        TrieNode {
            children: HashMap::new(),
            is_end_of_word: false,
        }
    }
}

pub struct Trie {
    root: TrieNode,
}

impl Trie {
    pub fn new() -> Trie {
        Trie { root: TrieNode::new() }
    }

    pub fn add_word(&mut self, word: &str) {
        let mut current_node = &mut self.root;
        for char in word.chars() {
            current_node = current_node.children.entry(char).or_insert(TrieNode::new());
        }
        current_node.is_end_of_word = true;
    }

    pub fn delete_word(&mut self, word: &str) {
        self.depth_first_delete(&mut self.root, word, 0);
    }

    fn depth_first_delete(&mut self, current_node: &mut TrieNode, word: &str, index: usize) -> bool {
        if index == word.len() {
            if !current_node.is_end_of_word {
                return false;
            }
            current_node.is_end_of_word = false;
            return current_node.children.is_empty();
        }

        let char = word.chars().nth(index).unwrap();
        let next_node = current_node.children.get_mut(&char);

        if let Some(next_node) = next_node {
            let should_delete_current_node = self.depth_first_delete(next_node, word, index + 1);

            if should_delete_current_node {
                current_node.children.remove(&char);
                return current_node.children.is_empty();
            }
        }

        false
    }

    pub fn depth_first_delete_iterative(&mut self, word: &str) {
        let mut current_node = &mut self.root;
        let mut index = 0;
        let mut nodes_stack: Vec<(&mut TrieNode, usize)> = Vec::new();

        while index < word.len() {
            if let Some(char) = word.chars().nth(index) {
                let next_node = current_node.children.get_mut(&char);

                if let Some(next_node) = next_node {
                    nodes_stack.push((current_node, index));
                    current_node = next_node;
                    index += 1;
                } else {
                    return;
                }
            }
        }

        current_node.is_end_of_word = false;

        while let Some((parent_node, parent_index)) = nodes_stack.pop() {
            if current_node.children.is_empty() && !current_node.is_end_of_word {
                parent_node.children.remove(&word.chars().nth(parent_index).unwrap());
            }

            current_node = parent_node;
        }
    }

    pub fn suggest_next_characters(&self, prefix: &str) -> Vec<char> {
        let last_node = self.get_last_character_node(prefix);
        let mut suggestions = Vec::new();
        if let Some(last_node) = last_node {
            self.suggest_next_characters_recursive(&last_node, prefix, &mut suggestions);
        }
        suggestions
    }

    fn suggest_next_characters_recursive(&self, node: &TrieNode, current_prefix: &str, suggestions: &mut Vec<char>) {
        if node.is_end_of_word {
            suggestions.push(current_prefix.chars().last().unwrap());
        }

        for (char, child_node) in &node.children {
            self.suggest_next_characters_recursive(child_node, &(current_prefix.to_owned() + char), suggestions);
        }
    }

    pub fn suggest_next_characters_iterative(&self, prefix: &str) -> Vec<char> {
        let mut suggestions = Vec::new();
        let mut current_node = &self.root;
        let mut current_prefix = String::new();

        for char in prefix.chars() {
            if let Some(next_node) = current_node.children.get(&char) {
                current_node = next_node;
                current_prefix.push(char);
            } else {
                return suggestions;
            }
        }

        let mut stack: Vec<(&TrieNode, String)> = Vec::new();
        stack.push((current_node, current_prefix.clone()));

        while let Some((node, current)) = stack.pop() {
            if node.is_end_of_word {
                suggestions.push(current.chars().last().unwrap());
            }

            for (char, child_node) in &node.children {
                stack.push((child_node, current.clone() + char));
            }
        }

        suggestions
    }

    pub fn does_word_exist(&self, word: &str) -> bool {
        let last_node = self.get_last_character_node(word);
        last_node.map_or(false, |node| node.is_end_of_word)
    }

    fn get_last_character_node(&self, prefix: &str) -> Option<&TrieNode> {
        let mut current_node = &self.root;
        for char in prefix.chars() {
            if let Some(next_node) = current_node.children.get(&char) {
                current_node = next_node;
            } else {
                return None;
            }
        }
        Some(current_node)
    }

    pub fn starts_with(&self, prefix: &str) -> bool {
        self.get_last_character_node(prefix).is_some()
    }
}

class Trie {
  private root: TrieNode;

  constructor() {
    this.root = new TrieNode();
  }

  addWord(word: string): void {
    let currentNode: TrieNode = this.root;
    for (const char of word) {
      currentNode = currentNode.children[char] ??= new TrieNode();
    }
    currentNode.isEndOfWord = true;
  }

  deleteWord(word: string): void {
    this.deleteWordRecursive(this.root, word, 0);
  }

  DeleteWordIterative(word: string): void {
    let currentNode: TrieNode = this.root;
    let index = 0;
    const nodesStack: Array<[TrieNode, number]> = [];

    while (index < word.length) {
      const char = word[index];
      const nextNode = currentNode.children[char];

      if (!nextNode) {
        return;
      }

      nodesStack.push([currentNode, index]);
      currentNode = nextNode;
      index++;
    }

    currentNode.isEndOfWord = false;

    while (nodesStack.length > 0) {
      const [parentNode, parentIndex] = nodesStack.pop()!;

      if (
        Object.keys(currentNode.children).length === 0 &&
        !currentNode.isEndOfWord
      ) {
        delete parentNode.children[word[parentIndex]];
      }

      currentNode = parentNode;
    }
  }

  depthFirstDelete(word: string): void {
    this.depthFirstDeleteRecursive(this.root, word, 0);
  }

  DeleteWordIterative(word: string): void {
    let currentNode: TrieNode = this.root;
    let index = 0;
    const nodesStack: Array<[TrieNode, number]> = [];

    while (index < word.length) {
      const char = word[index];
      const nextNode = currentNode.children[char];

      if (!nextNode) {
        return;
      }

      nodesStack.push([currentNode, index]);
      currentNode = nextNode;
      index++;
    }

    currentNode.isEndOfWord = false;

    while (nodesStack.length > 0) {
      const [parentNode, parentIndex] = nodesStack.pop()!;

      if (
        Object.keys(currentNode.children).length === 0 &&
        !currentNode.isEndOfWord
      ) {
        delete parentNode.children[word[parentIndex]];
      }

      currentNode = parentNode;
    }
  }

  suggestNextCharacters(prefix: string): string[] {
    const lastNode = this.getLastCharacterNode(prefix);
    const suggestions: string[] = [];
    if (lastNode) {
      this.suggestNextCharactersRecursive(lastNode, prefix, suggestions);
    }
    return suggestions;
  }

  suggestNextCharactersIterative(prefix: string): string[] {
    const suggestions: string[] = [];
    let currentNode: TrieNode = this.root;
    let currentPrefix = "";

    for (const char of prefix) {
      currentNode = currentNode.children[char];
      if (!currentNode) {
        return suggestions;
      }
      currentPrefix += char;
    }

    const stack: Array<[TrieNode, string]> = [[currentNode, currentPrefix]];

    while (stack.length > 0) {
      const [node, current] = stack.pop()!;

      if (node.isEndOfWord) {
        suggestions.push(current.charAt(current.length - 1));
      }

      for (const [char, childNode] of Object.entries(node.children)) {
        stack.push([childNode, current + char]);
      }
    }

    return suggestions;
  }

  doesWordExist(word: string): boolean {
    const lastNode = this.getLastCharacterNode(word);
    return lastNode?.isEndOfWord ?? false;
  }

  startsWith(prefix: string): boolean {
    return this.getLastCharacterNode(prefix) !== undefined;
  }

  private deleteWordRecursive(
    currentNode: TrieNode | undefined,
    word: string,
    index: number,
  ): boolean {
    if (!currentNode) {
      return false;
    }

    if (index === word.length) {
      if (!currentNode.isEndOfWord) {
        return false;
      }
      currentNode.isEndOfWord = false;
      return Object.keys(currentNode.children).length === 0;
    }

    const char = word[index];
    const nextNode = currentNode.children[char];

    if (!nextNode) {
      return false;
    }

    const shouldDeleteCurrentNode = this.deleteWordRecursive(
      nextNode,
      word,
      index + 1,
    );

    if (shouldDeleteCurrentNode) {
      delete currentNode.children[char];
      return Object.keys(currentNode.children).length === 0;
    }

    return false;
  }

  private depthFirstDeleteRecursive(
    currentNode: TrieNode,
    word: string,
    index: number,
  ): void {
    if (index === word.length) {
      currentNode.isEndOfWord = false;
      return;
    }

    const char = word[index];
    const nextNode = currentNode.children[char];

    if (!nextNode) {
      return;
    }

    this.depthFirstDeleteRecursive(nextNode, word, index + 1);

    if (Object.keys(nextNode.children).length === 0 && !nextNode.isEndOfWord) {
      delete currentNode.children[char];
    }
  }

  private suggestNextCharactersRecursive(
    node: TrieNode,
    currentPrefix: string,
    suggestions: string[],
  ): void {
    if (node.isEndOfWord) {
      suggestions.push(currentPrefix.charAt(currentPrefix.length - 1));
    }

    for (const [char, childNode] of Object.entries(node.children)) {
      this.suggestNextCharactersRecursive(
        childNode,
        currentPrefix + char,
        suggestions,
      );
    }
  }

  private getLastCharacterNode(prefix: string): TrieNode | undefined {
    let currentNode: TrieNode = this.root;
    for (const char of prefix) {
      currentNode = currentNode.children[char];
      if (!currentNode) {
        return undefined;
      }
    }
    return currentNode;
  }
}

class TrieNode {
  children: Record<string, TrieNode>;
  isEndOfWord: boolean;

  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}