# Count Total words in Trie

The problem involves working with a trie data structure to determine the total number of words it contains. A trie (also known as a prefix tree) is a tree-like data structure used to store a dynamic set of strings. Each node of the trie represents a single character of a string, and paths from the root to a node represent the characters in a string. The problem here is to count the total number of complete words present in the trie.

## Problem Statement

Given a trie containing various words, the task is to count the total number of complete words present in the trie.

## Description with Example

Consider a scenario where we have a trie containing the words: "how," "many," "code," "co," "club," "run," "rule," and "set." The trie would look like this:

``````           root

/  / |  \    \
/  /  |   \    \
/  /   |    \    \
h   m   c     r    s
|   |   | \   |    |
o   a   o  l  u    e
|   |   |  |  | \  |
w   n   d  u  n  l t
|   |  |     |
y   e  b     e
``````

## Idea to Solve the Problem The idea to solve this problem is to recursively traverse the trie and count the nodes where the `end` flag is set to true. The `end` flag indicates the end of a complete word.

## Pseudocode

``````function countWords(node):
if node is not null:
counter = 0
if node.end is true:
increment counter
for each child in node's children:
increment counter by countWords(child)
return counter
return 0``````

## Algorithm Explanation

1. Define a `Node` class to represent nodes in the trie. Each node has a boolean variable `end` to mark the end of a word and an array `children` to store references to its child nodes.

2. Define a `Trie` class to encapsulate the trie structure. The `Trie` class has a `root` node as its member.

3. Implement the `insert` function in the `Trie` class to insert a word into the trie. This function iterates through the characters of the word, creating new nodes as necessary.

4. Implement the `words` function in the `Trie` class to recursively count the complete words in the trie. This function starts from the root and traverses through the children nodes, incrementing the counter whenever the `end` flag is true.

5. In the `main` function, create an instance of the `Trie` class, insert the words, and then call the `words` function to count the total number of complete words.

## Code Solution

``````//C++ program
//Count Total words in Trie
#include <iostream>
#include <string.h>
using namespace std;
#define ALPHABETS 26
struct Node
{
//Indicates end of string
int end;
struct Node *children[ALPHABETS];
};

class Trie
{

public:
Node *root;
Trie()
{
root = new Node;

for (int i = 0; i < ALPHABETS; ++i)
{
root->children[i]=NULL;
}
root->end=0;
}
void insert(string);
int  words(Node *root);

};

void Trie:: insert(string text)
{
//First get the length of text
int length = text.size();

//This variable are used to task find the index location of character
int index = 0;

//Get the root node

for (int level = 0; level < length ; level++ )
{

//Get the index
index = text[level]-'a';

{
//When need to add new Node

for (int i = 0; i < ALPHABETS; ++i)
{
}
}

}
{
//Indicates end of string
}

}

int Trie:: words(Node *root)
{
int counter = 0;
if(root!=NULL)
{

if(root->end==1)
{
counter++;
}
for (int i = 0; i < ALPHABETS ; i++ )
{
if(root->children[i] != NULL)
{
counter += words(root->children[i]);
}
}

}
return counter;
}
int main()
{
//Make object
Trie obj ;
obj.insert("how");
obj.insert("many");
obj.insert("code");
obj.insert("co");
obj.insert("club");
obj.insert("run");
obj.insert("rule");
obj.insert("set");

/*
root

/  / |  \    \
/  /  |   \    \
/  /   |    \    \
h   m   c     r    s
|   |   | \   |    |
o   a   o  l  u    e
|   |  /|  |  | \  |
w   n # d  u  n  l t
|   |  |     |
y   e  b     e
*/
cout<<" Total Words : "<<obj.words(obj.root);

return 0;
}``````

#### Output

``Total Words : 8``
``````/*
Java program
Count Total words in Trie
*/
class Node
{
//Indicates end of string
public boolean end;

public Node []children;

public Node(int size)
{
children = new Node[size];
end = false;
}
}
public class Trie
{
static final int ALPHABETS = 26;

public Node root;

public Trie()
{
root = new Node(ALPHABETS);
}

public void insert(String text)
{
//First get the length of text
int length = text.length();

//This variable are used to task find the index location of character
int index = 0;

//Get the root node

for (int level = 0; level < length ; level++ )
{
//Get the index
index = text.charAt(level)-'a';

{
//When need to add new Node
}

}
{
//indicates end of string
}
}
public int words(Node root)
{
int counter = 0;
if(root!=null)
{

if(root.end==true)
{
counter++;
}
for (int i = 0; i < ALPHABETS ; i++ )
{
if(root.children[i] != null)
{
counter += words(root.children[i]);
}
}

}
return counter;
}

public static void main(String[] args)
{
//Make object
Trie obj = new Trie();

obj.insert("how");
obj.insert("many");
obj.insert("code");
obj.insert("co");
obj.insert("club");
obj.insert("run");
obj.insert("rule");
obj.insert("set");

/*
root

/  / |  \    \
/  /  |   \    \
/  /   |    \    \
h   m   c     r    s
|   |   | \   |    |
o   a   o  l  u    e
|   |  /|  |  | \  |
w   n # d  u  n  l t
|   |  |     |
y   e  b     e
*/

System.out.println(" Total Words : "+obj.words(obj.root));

}
}``````

#### Output

`` Total Words : 8``
``````#Python program
#Count Total words in Trie
class Node:
def __init__(self,size):
self.children=[None]*size
self.end=False

class Trie:

def __init__(self):
self.ALPHABET = 26
self.root=Node(self.ALPHABET)

def insert(self,text) :

#First get the length of text
length=len(text)
#This variable are used to task find the index location of character
index=0
#Get the root node
level=0
while ( level< length  ) :

#Get the index
index=ord(text[level])-ord('a')

#When need to add new Node

level+=1

#Indicates end of string

def words(self,root) :

counter = 0
if(root!=None) :

if(root.end==True) :

counter += 1
i = 0
while (i < self.ALPHABET )  :

if(root.children[i] != None) :

counter += self.words(root.children[i])
i += 1
return counter

def main():
obj = Trie()

obj.insert("how")
obj.insert("many")
obj.insert("code")
obj.insert("co")
obj.insert("club")
obj.insert("run")
obj.insert("rule")
obj.insert("set")
#
#         root
#     /  / |  \    \
#    /  /  |   \    \
#   /  /   |    \    \
#  h   m   c     r    s
#  |   |   | \   |    |
#  o   a   o  l  u    e
#  |   |  /|  |  | \  |
#  w   n # d  u  n  l t
#      |   |  |     |
#      y   e  b     e
#
print(" Total Words : ",obj.words(obj.root))

if __name__=="__main__":
main()``````

#### Output

`` Total Words :  8``
``````/*
C# program
Count Total words in Trie
*/
using System;
public class Node
{
//Indicates end of string
public Boolean end;

public Node []children;

public Node(int size)
{
children = new Node[size];
end = false;
}
}
public class Trie
{
public const int ALPHABETS = 26;

public Node root;

public Trie()
{
root = new Node(ALPHABETS);
}

public void insert(String text)
{
//First get the.Length of text
int length = text.Length;

//This variable are used to task find the index location of character
int index = 0;

//Get the root node

for (int level = 0; level < length ; level++ )
{
//Get the index
index = text[level]-'a';

{
//When need to add new Node
}

}
{
//indicates end of string
}
}
public int words(Node root)
{
int counter = 0;
if(root!=null)
{

if(root.end==true)
{
counter++;
}
for (int i = 0; i < ALPHABETS ; i++ )
{
if(root.children[i] != null)
{
counter += words(root.children[i]);
}
}

}
return counter;
}

public static void Main(String[] args)
{
//Make object
Trie obj = new Trie();

obj.insert("how");
obj.insert("many");
obj.insert("code");
obj.insert("co");
obj.insert("club");
obj.insert("run");
obj.insert("rule");
obj.insert("set");

/*
root

/  / |  \    \
/  /  |   \    \
/  /   |    \    \
h   m   c     r    s
|   |   | \   |    |
o   a   o  l  u    e
|   |  /|  |  | \  |
w   n # d  u  n  l t
|   |  |     |
y   e  b     e
*/

Console.WriteLine(" Total Words : "+obj.words(obj.root));

}
}``````

#### Output

`````` Total Words : 8
``````
``````<?php
/*
* PHP Program
* Count Total words in Trie
*/

class Node
{
public \$end;
public \$children;
function __construct(\$size)
{
\$this->children=array_fill(0, \$size, NULL);
\$this->end=false;

}
}
class Trie
{

public \$root;
const ALPHABET = 26;

function __construct()
{
\$this->root=new Node(self:: ALPHABET);
}

public function  insert(\$text)
{
//First get the length of text
\$length=strlen(\$text);

//This variable are used to task find the index location of character
\$index=0;

//Get the root node

for (\$level=0; \$level< \$length; ++\$level)
{

//Get the index
\$index=ord(\$text[\$level])-ord('a');

{
//When need to add new Node
}

}
{
//Indicates end of string
}
}
public function words(\$root)
{
\$counter = 0;
if(\$root!=NULL)
{

if(\$root->end==true)
{
\$counter++;
}
for ( \$i = 0; \$i < self::ALPHABET ; \$i++ )
{
if(\$root->children[\$i] != NULL)
{
\$counter += \$this->words(\$root->children[\$i]);
}
}

}
return \$counter;
}

}

function main()
{
//Make object
\$obj = new Trie();

\$obj->insert("how");
\$obj->insert("many");
\$obj->insert("code");
\$obj->insert("co");
\$obj->insert("club");
\$obj->insert("run");
\$obj->insert("rule");
\$obj->insert("set");

/*
root

/  / |  \    \
/  /  |   \    \
/  /   |    \    \
h   m   c     r    s
|   |   | \   |    |
o   a   o  l  u    e
|   |  /|  |  | \  |
w   n # d  u  n  l t
|   |  |     |
y   e  b     e
*/
echo " Total Words : ".\$obj->words(\$obj->root);
}
main();
?>``````

#### Output

`` Total Words : 8``

## Time Complexity

The time complexity of inserting a word into the trie is O(N), where N is the length of the word. The time complexity of the `words` function is O(N), where N is the number of nodes in the trie. Since each node corresponds to a character, the number of nodes is proportional to the number of characters. Therefore, the overall time complexity of the code is O(N), where N is the total number of characters in the trie.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.