DropDown tree with search

Question

I fetch a bunch of categories for a DropDown tree, and have to implement search in this dropdown. If there is a match in one of the elements, it should also get all parents to display in the dropdown hierarchy. The number of childnodes is unknown, and can be changed at any given time (example has only 3 levels but can be 5 also).

The search applies on every ScrapCategory description.

I get the expected result but I would love to see this in \$O(N)\$.

public sealed class ScrapCategory
{
    public int Id { get; set; }

    public bool IsActive { get; set; }

    public string Description { get; set; }

    public int Level { get; set; }

    public int ParentId { get; set; }
}

public ScrapCategory[] Filter(ScrapCategory[] categories, string searchString)
{
    var result = new List<ScrapCategory>();

    foreach (ScrapCategory category in categories)
    {
        if (category.Description.IndexOf(searchString, StringComparison.OrdinalIgnoreCase) >= 0)
            result.Add(category);

        if (category.ParentId > 0)
        {
            int parentId = category.ParentId;

            while (parentId > 0)
            {
                var parent = categories.Where(x => x.Id == parentId)?.First();
                if (!result.Contains(parent))
                    result.Add(parent);
                parentId = parent.ParentId;
            }
        }
    }

    return result.OrderBy(x => x.Level).ToArray();
}

Answer 1

    var result = new List<ScrapCategory>();
    ...
                if (!result.Contains(parent))

There's one performance problem. Use a data structure which gives fast Contains checks: typically HashSet<>.

---

                var parent = categories.Where(x => x.Id == parentId)?.First();

There's another one. I assume that IDs are unique, in which case lookup = categories.ToDictionary(category => category.Id) will give you a fast hash map from ID to category.

---

        if (category.Description.IndexOf(searchString, StringComparison.OrdinalIgnoreCase) >= 0)
            result.Add(category);

        if (category.ParentId > 0)
        {
            int parentId = category.ParentId;

            while (parentId > 0)
            {
                ...
            }
        }

Is this definitely correct? It's not supposed to be

        if (category.Description.IndexOf(searchString, StringComparison.OrdinalIgnoreCase) >= 0)
        {
            result.Add(category);

            if (category.ParentId > 0)
            {
                ...
            }
        }

?

Either way, the if (category.ParentId > 0) is pointless. The test is repeated by the while loop, and a single assignment to a local variable isn't going to be a performance bottleneck.

---

                if (!result.Contains(parent))
                    result.Add(parent);

Note that with the suggestion of making result a HashSet it becomes preferable to just call Add, which returns a bool to tell you whether it changed anything. If it didn't, you can break out of the loop, because you know that all of the further ancestors have already been added.

---

The effect of these changes (except the one I'm unsure about) is

public ScrapCategory[] Filter(ScrapCategory[] categories, string searchString)
{
    var lookup = categories.ToDictionary(category => category.Id);
    var result = new HashSet<ScrapCategory>();

    foreach (ScrapCategory category in categories)
    {
        if (category.Description.IndexOf(searchString, StringComparison.OrdinalIgnoreCase) >= 0)
            result.Add(category);

        int parentId = category.ParentId;
        while (parentId > 0)
        {
            var parent = lookup[parentId];
            if (!result.Add(parent))
                break;
            parentId = parent.ParentId;
        }
    }

    return result.OrderBy(x => x.Level).ToArray();
}

Answer 2

A possibility is to store the parents as we go so we don't need to keep searching though the input array.
We can use a dictionary to look up the parents by id.

If we can guarantee that the ancestors for a category all appear in the array before the category then we can do this in one pass.

Reading through the array we add each category to the dictionary, keyed to its id. We can also use the dictionary entry to show if a given item has already been added to the result (this removes the need for the Contains() check)

Then, if it has a parent, we get the parent from the dictionary and if it hasn't been added, add it, and then repeat for the parent't parent (if any), recursing up the tree.

private static Category[] Filter(IEnumerable<Category> categories, string searchString)
{
    var ret = new List<Category>();
    var dict = new Dictionary<int, DictEntry>();
    foreach (var category in categories)
    {
        dict.Add(category.Id, new DictEntry(category));
        if (category.Description.IndexOf(searchString, StringComparison.OrdinalIgnoreCase) >= 0)
        {
            ret.Add(category);
            dict[category.Id].Added = true;

            var parentId = category.ParentId;

            while (true)
            {
                if (parentId == 0) break;
                var parent = dict[parentId].Category;

                if (!dict[parent.Id].Added)
                {
                    ret.Add(parent);
                    dict[parent.Id].Added = true;
                }
                parentId = parent.ParentId;

            }
        }
    }
    return ret.OrderBy(n => n.Level).ToArray();
}

If we cannot guarantee that the ancestors appear ahead of the category then we can do it in two passes. Not O(N) (AFAIK) but still should be notably faster than searching all the inputs for each ancestor.

private Category[] Filter(IEnumerable<Category> categories, string searchString)
{
    var ret = new List<Category>();
    var dict = new Dictionary<int, DictEntry>();
    foreach(var category in categories)
    {
        dict.Add(category.Id, new DictEntry(category));
        if(category.Description.IndexOf(searchString, StringComparison.OrdinalIgnoreCase) >=0)
        {
            ret.Add(category);
            dict[category.Id].Added = true;
        }
    }

    var ancestors = new List<Category>();
    foreach(var category in ret)
    {
        var parentId = category.ParentId;

        while(true)
        {
            if (parentId == 0) break;
            var parent = dict[parentId].Category;

            if(!dict[parent.Id].Added)
            {
                ancestors.Add(parent);
                dict[parent.Id].Added = true;
            }
            parentId = parent.ParentId;

        }

    }
    return ret.Concat(ancestors).OrderBy(n => n.Level).ToArray();
}

Other points:

I would push for having the input being IEnumerable<ScrapCategory> rather than ScrapCategory[]. The array requirement limits without adding anything useful.

Edit - Add missing helper class

class DictEntry
{
    public DictEntry(Category category)
    {
        Category = category;
        Added = false;
    }
    public Category Category { get; }
    public bool Added { get; set; }
}