Making a Trie Node class

Creation of Trie node Class

Introduction to Tries

Trie is a fascinating and powerful tree-like structure that finds its applications in various fields, including spell checkers, autocomplete systems, and IP routing.

To harness the full potential of a Trie, one must understand the importance of a Trie Node class.

In this article, we will delve into the Making of a Trie Node class, step by step, making it easier for you to implement this essential data structure in your projects.

What is trie? 

  • Tries are tree-like data structures that are particularly useful for solving problems related to strings and text.
  • The name “Trie” comes from the word “retrieval” because these structures excel at retrieving data associated with a specific key or prefix.
  • Tries are prominently used in various applications, such as autocomplete systems, spell checkers, and IP routing tables.

Why Do You Need a Trie Node Class?

The Trie data structure consists of nodes, and each node represents a single character of a string. A Trie Node class encapsulates the properties and methods necessary for building a Trie efficiently.

Trie data structure in Python

Here's a step-by-step guide to Making a trie Node Class:

Step 1: Define the TrieNode Class

Our first step is to define the TrieNode class. This class will have the following attributes:

  • children: A dictionary to store child nodes.
  • is_end_of_word: A boolean flag indicating if the node represents the end of a word.
  • word_count: An integer to keep track of the number of words sharing this node.
Step 2: Initialize the TrieNode Class
  • In the __init__ method of the TrieNode class, we initialize the attributes. The children attribute starts as an empty dictionary, is_end_of_word as False, and word_count as 0.
Step 3: Insertion Method
  • We need a method to insert words into the Trie. Let’s call it insert_word. This method will take a string as input and insert it into the Trie, creating nodes as needed.
Step 4: Search Method
  • A Trie is incomplete without a search functionality. Implement a insert_word. method to check if a given word exists in the Trie.
Step 5: Count Prefix Method
  • To count the number of words with a given prefix, we’ll create a count_prefix method.
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False
        self.word_count = 0

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

    def insert_word(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.word_count += 1
        node.is_end_of_word = True

    def search_word(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def count_prefix(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return 0
            node = node.children[char]
        return node.word_count

# Example usage:
trie = Trie()

print(trie.search_word("apple"))  # True
print(trie.search_word("apples"))  # False
print(trie.count_prefix("ap"))    # 3 (apple, app, apricot)
print(trie.count_prefix("ban"))   # 1 (banana)



This code defines a Trie data structure with methods to insert words, search for words, and count the number of words with a given prefix.


Creating a Trie Node class is a crucial step in harnessing the power of the Trie data structure. With this step-by-step guide, you now have the knowledge to build a Trie Node class from scratch, allowing you to implement Tries in your projects with confidence.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription