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

Solution Review: Finding All Words Stored in Trie

Explore the recursive method for finding all words stored in a trie structure in C#. Understand how to traverse each node, build words dynamically, and store results efficiently. This lesson helps you grasp trie traversal and string retrieval essential for coding interviews.

We'll cover the following...

Solution: Recursion

C#
using System;
using System.Collections.Generic;
using System.Text;
namespace chapter_7
{
    class Program
    {
        static void getWords(TrieNode root, List<string>  result, int level, ref string word)
        {
            //Leaf denotes end of a word
            if (root.isEndWord)
            {
                //current word is stored till the 'level' in the word string
                string temp = "";
                for (int x = 0; x < level; x++)
                {
                    temp += word[x];
                }
                result.Add(temp);
            }
            for (int i = 0; i < 26; i++)
            {
                if (root.children[i] != null)
                {
                    if(level < word.Length)
                    {
                        StringBuilder sb = new StringBuilder(word);
                        sb[level] = (char)(i + 'a');
                        word = sb.ToString();
                    }
                    else
                    {
                        word += (char)(i + 'a');
                    }
                    getWords(root.children[i], result, level + 1, ref word);
                }
            }
        }
        static List<string> findWords(TrieNode root)
        {
            List<string> result = new List<string> () ;
            string word = "";
            getWords(root, result, 0,ref  word);
            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]);
            }
            List<string> ans = findWords(t.getRoot());
            for (int i = 0; i < ans.Count; i++)
            {
                Console.WriteLine( ans[i] );
            }
            return;
        }
    }
}

The findWords(root) function contains a result vector that will contain all the words in the trie. word is a character array in which node characters are added one by one to keep track of all the alphabets in the same recursive call.

getWords() is your recursive function, which begins from the root and traverses every node. Whenever a node is the end of a word, temp (containing the character array) is converted into a string and inserted into a result.

Since the word cannot be reset before recording every new word, simply update the values at each index using the level.

Time complexity

As the algorithm traverses all the nodes, its run time is O(n) where n is the number of nodes in the trie.