Tree, directed acyclic graph

A directed acyclic graph contains nodes that do not form cycles. It can be used to store strings from a word list—each letter is one node.

For search performance, an optimized tree is often the best solution. It has an initialization cost. And it requires some extra code to create. The C# version here is not optimal.

Example code

In the C# language a tree can be implemented with classes (nodes) that point to further nodes. In this simple implementation, we use a Dictionary.

using System;
using System.Collections.Generic;

class DictionaryNodeRoot
{
    DictionaryNode _root = new DictionaryNode();

    public void AddWord(string value)
    {
        // Add nodes from string chars.
        DictionaryNode current = this._root;
        for (int i = 0; i < value.Length; i++)
        {
            current = current.Add(value[i]);
        }
        // Set state.
        current.SetWord(value);
    }

    public bool ContainsWord(string value)
    {
        // Get existing nodes from string chars.
        DictionaryNode current = this._root;
        for (int i = 0; i < value.Length; i++)
        {
            current = current.Get(value[i]);
            if (current == null)
            {
                return false;
            }
        }
        // Return state.
        return current != null && current.GetWord() != null;
    }
}

class DictionaryNode
{
    string _word;
    Dictionary<char, DictionaryNode> _dict; // Slow.

    public DictionaryNode Add(char value)
    {
        // Add individual node as child.
        // ... Handle null field.
        if (this._dict == null)
        {
            this._dict = new Dictionary<char, DictionaryNode>();
        }
        // Look up and return if possible.
        DictionaryNode result;
        if (this._dict.TryGetValue(value, out result))
        {
            return result;
        }
        // Store.
        result = new DictionaryNode();
        this._dict[value] = result;
        return result;
    }

    public DictionaryNode Get(char value)
    {
        // Get individual child node.
        if (this._dict == null)
        {
            return null;
        }
        DictionaryNode result;
        if (this._dict.TryGetValue(value, out result))
        {
            return result;
        }
        return null;
    }

    public void SetWord(string word)
    {
        this._word = word;
    }

    public string GetWord()
    {
        return this._word;
    }
}

class Program
{
    static void Main()
    {
        // Create a tree.
        DictionaryNodeRoot tree = new DictionaryNodeRoot();
        // Add three words to the tree.
        tree.AddWord("dot");
        tree.AddWord("net");
        tree.AddWord("perls");

        // Search for strings in the tree.
        Console.WriteLine(tree.ContainsWord("perls"));
        Console.WriteLine(tree.ContainsWord("nothing"));
    }
}
True
False

Notes, AddWord

We add a string char-by-char with a for-loop in AddWord. The Add method from DictionaryNode.cs returns the newly-added or accessed node. We call Add repeatedly.

Notes, DictionaryNode

On each node, we use a Dictionary instance. The Dictionary provides references to child nodes. The string field tells us whether a complete word here exists.

This tree uses Dictionary fields for child nodes. It works with strings. Its design can be adapted to other value types. The nodes can be optimized with other representations.