DropDown tree with search 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&lt;ScrapCategory&gt;();

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

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

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

    return result.OrderBy(x =&gt; x.Level).ToArray();
}
var result = new List&lt;ScrapCategory&gt;();
    ...
                if (!result.Contains(parent))



There's one performance problem. Use a data structure which gives fast Contains checks: typically HashSet&lt;&gt;.




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



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




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

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

            while (parentId &gt; 0)
            {
                ...
            }
        }



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

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

            if (category.ParentId &gt; 0)
            {
                ...
            }
        }


?

Either way, the if (category.ParentId &gt; 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 =&gt; category.Id);
    var result = new HashSet&lt;ScrapCategory&gt;();

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

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

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