Today I want to talk about a cool little data structure called a “trie”. The trie gets its name from the word re/trie/val. A trie is a data structure for building memory efficient dictionaries with fast lookups. Tries are the foundation for one of the fastest known sorting algorithms (burstsort), it is also used for spell checking, and is used in applications that use text completion.

Let’s say I wanted to store the following words in a trie: to, tea, ted, ten, team, a, i, in, inn.

Note that the parent node is always null or empty.

To find the word /team/, we would traverse the trie starting at t > e > a > m*

To find the word /in/, we would go i > n*

If we were to search for the word /te/, it would return false because it doesn’t end on a node with a marker.

* indicates a marker for a complete word.

A complete word is indicated by a red star in the diagram. It is also marked by a boolean property in our implementation.

Our first class is the node which represents each node on the trie.

    public class Node
    {
        char _letter;
        bool _last;
        Dictionary<char, Node> _children;

        protected Node() { }

        public Node(char c)
        {
            _children = new Dictionary<char, Node>();
            _last = false;
            _letter = c;
        }

        public char Letter
        {
            get { return this._letter; }
            set { this._letter = value; }
        }

        public bool Last
        {
            get { return this._last; }
            set { this._last = value; }
        }

        public Dictionary<char, Node> Children
        {
            get { return this._children; }
            set { this._children = value; }
        }

        public Node ChildNode(char c)
        {
            if (Children != null)
            {
                if (Children.ContainsKey(c))
                {
                    return Children1;
                }
            }
            return null;
        }

        public override bool Equals(object obj)
        {
            if (obj == null || this.GetType() != obj.GetType())
                return false;
            
            return Equals(obj);
        }
        
        public bool Equals(Node obj)
        {
            if (obj != null
                && obj.Letter == this.Letter)
            {
                return true;
            }               

            return false;
        }

        public override int GetHashCode()
        {
            int hash = 13;
            hash = (hash * 7) + this.Letter.GetHashCode();
            return hash;
        }
    }

*Edit: updated node class to use a dictionary for faster searches.

Our next class is our actual Trie, it contains each node and only has two operations – inserting and searching.

    public class Trie
    {
        private Node _root;

        public Trie()
        {
            _root = new Node(' ');
        }

        public void Insert(string s)
        {
            char[] word = s.ToLower().ToCharArray();

            Node current = _root;

            if (word.Length == 0)
            {
                current.Last = true;
            }

            for (int i = 0; i < s.Length; i++)
            {
                Node child = current.ChildNode(word[i]);
                if (child != null)
                {
                    current = child;
                }
                else
                {
                    current.Children.Add(word[i], new Node(word[i]));
                    current = current.ChildNode(word[i]);
                }

                if (i == word.Length - 1)
                {
                    current.Last = true;
                }
            }
        }

        public bool Search(string s)
        {
            char[] word = s.ToLower().ToCharArray();
            Node current = _root;
            while (current != null)
            {
                for (int i = 0; i < word.Length; i++)
                {
                    if (current.ChildNode(word[i]) == null)
                        return false;
                    else
                        current = current.ChildNode(word[i]);
                }

                if (current.Last == true)
                    return true;
                else
                    return false;
            }
            return false;
        }
    }

Implementation in a windows form application.

    public partial class MainForm : Form
    {
        Trie trie;

        public MainForm()
        {
            InitializeComponent();
        }

        private void MainForm_Load(object sender, EventArgs e)
        {
            trie = new Trie();
        }

        private void findButton_Click(object sender, EventArgs e)
        {
            if (trie.Search(findTextBox.Text.Trim()))
            {
                results.Text = String.Format("\"{0}\" was found in the trie.", findTextBox.Text);
            }
            else
            {
                results.Text = String.Format("\"{0}\" was not found in the trie.", findTextBox.Text);
            }

            findTextBox.Text = "";
        }

        private void insertButton_Click(object sender, EventArgs e)
        {
            string phrase = insertTextBox.Text.Trim();

            string[] words = phrase.Trim().Split(' ', ',', ';', '.');

            foreach (string word in words)
            {
                trie.Insert(word);
            }

            trie.Insert(phrase);

            results.Text = String.Format("\"{0}\" was successfully inserted into trie.", insertTextBox.Text);

            insertTextBox.Text = "";
        }

    }

Here’s the implementation in action.

Inserting words into trie.

Searching the trie for a word.

If a word isn’t in the trie then we would get a “false”.