Autocomplete using a trie

In this post I am going to show you how to implement autocomplete using jquery and Trie data structure.
Before going into code implementations lets understand what is trie.

A trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is a kind of search tree—an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are not necessarily associated with every node. Rather, values tend only to be associated with leaves, and with some inner nodes that correspond to keys of interest. For the space-optimized presentation of prefix tree, see compact prefix tree.
In the example shown, keys are listed in the nodes and values below them. Each complete English word has an arbitrary integer value associated with it. A trie can be seen as a tree-shaped deterministic finite automaton. Each finite language is generated by a trie automaton, and each trie can be compressed into a deterministic acyclic finite state automaton.(source wikipedia)

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);
<%@ 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" />
<?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);


How to create a simple Http Server in NodeJs

Node.js is an open source, cross-platform runtime environment for server-side and networking applications. Node.js applications are written in JavaScript and can be run within the Node.js runtime on OS X, Microsoft Windows, Linux.

Node.js uses the Google V8 JavaScript engine to execute code, and a large percentage of the basic modules are written in JavaScript. Node.js contains a built-in library to allow applications to act as a Web server without software such as Apache HTTP Server or IIS.
In this post I will show you how to create a simple Http Server using node.js Before diving into code let us first install node.js from following link.

Once the node.js installed.Open the terminal window and type following command.

node –version


If you see similar output then node.js is installed on your machine.

Open any text editor and paste following code into it and save it as Sever.js.


var http = require("http");

function requestHandler(req, res) {

	res.writeHead(200, { 'Content-Type': 'text/html' });
	res.write("Hello world");
	//end the response

//Create http server
var server = http.createServer(requestHandler);
server.listen(8000, function () {
	console.log("Server is up and running");

open command prompt and type following command.

node Server.js