Finding All Words Inside A String Using A Trie | Real world example

In this article, I am going to discuss how to implement autocomplete using jquery and Trie data structure.
Before going into code implementations, let’s understand what a trie is.

What is a trie

A trie, also called digital tree and sometimes radix tree or prefix tree (as prefixes can search them), is a kind of search tree—an ordered tree data structure that is used for pattern matching.
The trie has the following features

  • Each node but the root is labelled with a character.
  • Nodes are alphabetically ordered from left to right
  • The path from child to root yields the string

Open visual studio and create empty website project and add following code into App_Code


using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;

/// <summary>
/// Summary description for Trie
/// </summary>
public class Autocomplete

    // Trie node class
    public class Node
        public string Prefix { get; set; }
        public Dictionary<char, Node> Children { get; set; }

        // Does this node represent the last character in a word?
        public bool IsWord;

        public Node(String prefix)
            this.Prefix = prefix;
            this.Children = new Dictionary<char, Node>();

    // The trie
    private Node trie;

    // Construct the trie from the dictionary
    public Autocomplete(String[] dict)
        trie = new Node("");
        foreach (String s in dict)

    // Insert a word into the trie
    private void InsertWord(String s)
        // Iterate through each character in the string. If the character is not
        // already in the trie then add it
        Node curr = trie;
        for (int i = 0; i < s.Length; i++)
            if (!curr.Children.ContainsKey(s[i]))

                curr.Children.Add(s[i], new Node(s.Substring(0, i + 1)));
            curr = curr.Children[s[i]];
            if (i == s.Length - 1)
                curr.IsWord = true;

    // Find all words in trie that start with prefix
    public List<String> GetWordsForPrefix(String pre)
        List<String> results = new List<String>();

        // Iterate to the end of the prefix
        Node curr = trie;
        foreach (char c in pre.ToCharArray())
            if (curr.Children.ContainsKey(c))
                curr = curr.Children[c];
                return results;

        // At the end of the prefix, find all child words
        FindAllChildWords(curr, results);
        return results;

    // Recursively find every child word
    private void FindAllChildWords(Node n, List<String> results)
        if (n.IsWord)
        foreach (var c in n.Children.Keys)
            FindAllChildWords(n.Children[c], results);

Open the default.aspx and pate the following code. The code is self-explanotory.


<%@ Page Language="C#" AutoEventWireup="true" CodeFile="Default.aspx.cs" Inherits="_Default" %>

<!DOCTYPE html>

<html xmlns="">
<head runat="server">
    <script src="Scripts/jquery-1.12.4.js"></script>
    <script src="Scripts/jquery-ui-1.12.1.js"></script>
    <link href="Content/themes/base/jquery-ui.css" rel="stylesheet" />
    <script type="text/javascript">
            $(document).ready(function() {
            function SearchText() {
                    source: function(request, response) {
                            type: "POST",
                            contentType: "application/json; charset=utf-8",
                            url: "WebService.asmx/GetData",
                            data: "{'username':'" + document.getElementById('txtSearch').value + "'}",
                            dataType: "json",
                            success: function (data) {
                                if (data != null) {

                            error: function(result) {
    <form id="form1" runat="server">
          <div class="demo">
           <div class="ui-widget">
            <label for="tbAuto">Enter UserName: </label>
       <input type="text" id="txtSearch" class="autosuggest" />

Edit the web.config as per the below


<?xml version="1.0"?>

 For more information on how to configure your ASP.NET application, please visit


      <compilation debug="true" targetFramework="4.5.2" />
      <httpRuntime targetFramework="4.5.2" />
          <add name="HttpPost"/>



using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
using System.Web.Services;

/// <summary>
/// Summary description for WebService
/// </summary>
[WebService(Namespace = "")]
[WebServiceBinding(ConformsTo = WsiProfiles.BasicProfile1_1)]
// To allow this Web Service to be called from script, using ASP.NET AJAX, uncomment the following line. 
public class WebService : System.Web.Services.WebService

    public WebService()

        //Uncomment the following line if using designed components 

    public List<string> GetData(string username)
        Autocomplete a = new Autocomplete(new String[] { "india", "ireland", "usa", "poland", "uk", "germany", "guana", "uae" });

        return a.GetWordsForPrefix(username);

Next Post Previous Post
No Comment
Add Comment
comment url