Insert and Search Using Trie in Kotlin

A Trie (pronounced “try”) is a tree-like data structure used to efficiently store and retrieve a large set of strings or sequences of characters. It is also known as a digital tree or prefix tree.

In a Trie, each node represents a single character, and a path from the root node to any other node represents a string formed by concatenating the characters associated with the nodes along the path. The root node represents an empty string, and each leaf node represents a complete word or sequence.

Tries are particularly useful for fast string search and matching operations, such as auto-completion, spell checking, and pattern matching. They can be constructed and searched efficiently in O(m) time, where m is the length of the string being searched.

One of the main advantages of Tries over other data structures like hash tables or binary search trees is that they can handle operations on strings with common prefixes more efficiently. This is because Tries store prefixes as a single shared branch rather than duplicating them for each string, which saves memory and reduces the time complexity of common operations.

here is an example of how the Trie data structure would look like with the words “apple”, “banana”, and “orange” inserted:

        (root)
         / | \
        a  b  o
       /   |   \
      p    a    r
     /     |     \
    p      n      a
   /        \      \
  l          a      n
             |      |
             n      g
                    |
                    e

class TrieNode {
    val children = mutableMapOf<Char, TrieNode>()
    var isWord = false
}
class Trie {
    private val root = TrieNode()
    fun insert(word: String) {
        var current = root
        for (c in word) {
            current.children.getOrPut(c) { TrieNode() }
            current = current.children[c]!!
        }
        current.isWord = true
    }
    fun search(word: String): Boolean {
        var current = root
        for (c in word) {
            current = current.children[c] ?: return false
        }
        return current.isWord
    }
}
fun main() {
    val trie = Trie()
    trie.insert("apple")
    trie.insert("banana")
    trie.insert("orange")
    println(trie.search("apple")) // true
    println(trie.search("pear")) // false
}

this example, the TrieNode class represents a node in the Trie data structure, with a children map that maps each character to its child node and a isWord flag that indicates whether the current node represents the end of a word. The Trie class provides methods for inserting and searching strings in the Trie, using a root node to traverse the Trie starting from the root. The insert method inserts a new word by creating a new node for each character and setting the isWord flag for the final node, while the search method checks whether a given word is present in the Trie by traversing the Trie and returning the value of the isWord flag for the final node.