Trie Kotlin

Node

structure Node
Children Node[Alphabet-Size]
Is-Terminal Boolean
Value Data-Type
end structure
data class Node<Value>(
val children: MutableMap<Char, Node<Value>> = mutableMapOf(),
var value: Value? = null,
)

Insert

Search

Delete

  • null if the node was a leaf (was because the value was just deleted)
  • the deleted node itself, if it still has children (not a leaf)
  1. The return value is not needed. All it does is signal whether a node should be removed from its parent (no value & no children). The parent node can check that itself: child.children.isEmpty() && child.value == null. That alone simplifies the stop condition considerably:
    if (index == key.length) node.value = null.
  2. The second stop condition becomes a simple null check (use a scope function): node.children[key[index]]?.run { ... }.
  3. The check to remove the child from its parent and the actual removal becomes a one liner:
    if (children...) node.children.remove(key[index]).

Encore: Non-Recursive

Encore 2: Cleanup

Summary

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store