Search⌘ K
Home
Courses
Data Structures for Coding Interviews in C#

Solution Review: Total Number of Words in a Trie

Explore how to implement a recursive algorithm to count the total number of words in a Trie data structure by visiting nodes where words end. Understand the approach and its linear time complexity, suitable for efficient string retrieval and storage in C#.

We'll cover the following...

Solution: Increment recursively

C#
using System;
namespace chapter_7
{
    class Program
    {
        static int totalWords(TrieNode root)
        {
            int result = 0;
            // Leaf denotes end of a word
            if (root.isEndWord)
                result++;
            for (int i = 0; i < 26; i++)
                if (root.children[i] != null)
                    result += totalWords(root.children[i]);
            return result;
        }
        static void Main(string[] args)
        {
            string [] keys = { "the", "a", "there", "answer", "any", "by", "bye", "their", "abc" };
            Trie t = new Trie();
            // Construct trie       
            for (int i = 0; i < 9; i++)
            {
                t.insertNode(keys[i]);
            }
            Console.WriteLine( totalWords(t.getRoot()));
            return;
        }
    }
}

This is a straightforward algorithm. Starting ...