Find an item in the hierarchical list

Question

What would be the efficient way for finding and item in the list of type DirectoryItem as -

List<DirectoryItem> lstRootDirectory = GetAllRootLevelDirectories();

Each DirectoryItem has a Items (list of same type- DirectoryItem) and DirectoryItem is a struct as below:

struct DirectoryItem
        {
          public string AbsolutePath { get { return string.Format("{0}/{1}", BaseUri, Name); } }
          public bool IsDirectory;
          public string Name;   
          public List<DirectoryItem> Items;  
        }

In this case, what would be better approach to find-out an item from this kind of hierarchical list.

score 1 · Answer 1 · answered Mar 03 '15 at 08:53

1

Your data structure is actually a directed tree.

Any tree-traversal algorithm will do to find all root level directories, such as:

Level order (BFS)
Post Order / Pre Order (variants of DFS)

answered Mar 03 '15 at 08:53

amit

175,853
27
231
333

score 1 · Answer 2 · answered Mar 03 '15 at 08:58

If you want to find items that are nested you can use recursion, something like this if you are searching after the name of the items

private void searchAll(DirectoryItem root, string name)
{
    for (int a = 0; a < root.Items.Count; a++)
    {
        if (name == root.Items[a].Name)
        {
            //
        }
        searchAll(root.Items[a], name);
    }
}

score 1 · Answer 3 · answered Mar 03 '15 at 09:07

1

You could also flatten the tree structure into a list and then do a search on the list using Linq.

Create an extension method:

public static IEnumerable<T> Flatten<T>(this IEnumerable<T> e, Func<T, IEnumerable<T>> f)
{
    return e.SelectMany(c => f(c).Flatten(f)).Concat(e);
}

Use the extension method:

IEnumerable<DirectoryItem> allDirectories = lstRootDirectory.Flatten(d => d.Items).ToList();

Now execute a LINQ where to find your DirectoryItem.

answered Mar 03 '15 at 09:07

Praveen Paulose

5,741
1
15
19

I have already searched on stackoverflow and looking for an efficient approach. http://stackoverflow.com/questions/11830174/how-to-flatten-tree-via-linq – Anil Kumar Mar 03 '15 at 09:15
This is just an easier approach. Your other option is write a recursive method either Depth First or Breadth First which may be more efficient depending on the nature of data, the information you are searching for and the number of results expected. – Praveen Paulose Mar 03 '15 at 09:24
Yes, as Amit suggest those are fine approaches! BTW, at present, I have recursive approach looks like _Vajura_ and it seems better than **Linq**. – Anil Kumar Mar 03 '15 at 09:33

Find an item in the hierarchical list

3 Answers3