Trie data structure
Trie DS

Trie data structure

Today I will write about a magical data structure namely Trie.

When we talk of storing and retriving some information about a bunch of strings, Trie comes to our rescue.

Basically Trie consists of a root TrieNode and 26 children. Each child in turn represents a TrieNode with another set of 26 children and so on.

Suppose we want to store a word "sid" in our trie data structure, so initially we place our pointer at the root and move from the root to the - ('s' - 'a')th indexed child of the root and place the 's' over there, then we move our pointer to the created 's' node and add another node at ('i' - 'a')th child of the 's' node and similarly we do it for the last 'd' character as well after moving our pointer to the created 'i' node.

Explaining the above through the below code -

Trie

The additional boolean namely isWordEnd to denote if a string ends at this node.

Now it is time to see the code to insert a word into the trie -

Insert a word into

After inserting the words into the Trie, next purpose is to search for the word in the Trie, algorithm that is popularly used in implementing dictionary, word suggestions etc.

Let us see the code for it -

Search for a word in

Finally combining everything, let us see how do we leverage the above code for our purpose -


Insert

The Time Complexity for both Inserting and Searching is O(n), where n is the length of the string being inserted or being searched for.

The Space Complexity for Inserting a word is O(n), where n is the length of the string being inserted. Whereas for searching for a word in a Trie, we do not require any auxilliary space(O(1)).

Through this article I wanted to explain the basics of the Trie data structure and its implementation. We can build on it, I would encourage the readers to implement more things on top of these and solve bigger problems using this magical data structure. Happy coding.


要查看或添加评论,请登录

Siddhant Mishra的更多文章

  • SuspendCoroutine

    SuspendCoroutine

    Today I will be writing about the usage of an important concept in Android namely suspendCoroutine. By definition…

  • findViewById - Internals

    findViewById - Internals

    Hope everyone is doing well. Today I will be writing about the internal working of findViewById in Android.

    2 条评论
  • Lambda functions

    Lambda functions

    Today I will be writing about two different yet intriguing way to write the lambda functions in Kotlin. Conventionally…

    1 条评论
  • Exceptions in Coroutines

    Exceptions in Coroutines

    Hi everyone, today I will be writing about exceptions in Coroutine and how to handle them gracefully. First let us see…

  • Vertical Order traversal in binary tree

    Vertical Order traversal in binary tree

    We generally talk about Inorder, PreOrder, PostOrder and LevelOrder traversals in binary tree, but we generally do not…

  • LCA in Binary Tree

    LCA in Binary Tree

    Today I will be writing about the LCA(Least Common Ancestor) for a binary tree. LCA refers to the node in the binary…

  • Delegates in Kotlin

    Delegates in Kotlin

    Today I will be writing about my understanding regarding the delegates in Kotlin. The english meaning of Delegation…

  • TypeAlias in Kotlin

    TypeAlias in Kotlin

    Today I will be writing about TypeAlias in Kotlin and how do I understand and use it in my day to day coding. Typealias…

  • Reified in Kotlin

    Reified in Kotlin

    Today I will be writing about the type erasure in Java and Kotlin and its solution. The concept of type erasure stems…

    1 条评论
  • Jetpack Compose - Interesting features to dive deeper into.

    Jetpack Compose - Interesting features to dive deeper into.

    Recently I got to migrate my sample project from the conventional XML to Jetpack Compose, and I would like to list down…

    3 条评论

社区洞察

其他会员也浏览了