Recursively search nested lists

c# list recursion

11,836

public class AccessibleTreeItem
{
    public string name;
    public List<AccessibleTreeItem> children;

    public AccessibleTreeItem()
    {
        children = new List<AccessibleTreeItem>();
    }

    public static AccessibleTreeItem Find(AccessibleTreeItem node, string name)
    {

        if (node == null)
            return null;

        if (node.name == name)
            return node;

        foreach (var child in node.children)
        {
            var found = Find(child, name);
            if (found != null)
                return found;
        }

        return null;
    }
}

11,836

Author by

HeWhoWas

Updated on August 12, 2022

Comments

HeWhoWas almost 2 years
I've read and searched and I'm yet to figure out an answer to this relatively simple issue.

I have a class:
```
public class AccessibleTreeItem
{
    public string name;
    public List<AccessibleTreeItem> children;

    public AccessibleTreeItem()
    {
        children = new List<AccessibleTreeItem>();
    }
}
```
which is populate using a series of functions that don't really matter in this context, but what I'm looking for is a way to search through ALL of the children items in the list, searching for a particular 'name' value, and if found, returning that List.

How is this achieved in the easiest manner, with the least performance hit? Thanks - I've been stumped at this point for days now...
Henk Holterman almost 13 years

Right, but this is a Depth-first search. It might be more efficient to check all Children before recursing.
Petar Ivanov almost 13 years

So you are saying DFS is less efficient, than BFS... Hm, no - they are exactly the same - both traverse by visiting each node only once. If you don't want to have recursion, you can do both BFS and DFS iteratively.
HeWhoWas almost 13 years

I've tested the code, and for some reason it always returns null? I set breakpoints and checked the AccessibleTreeItem node manually - the child object is there, but it's nested within 4 levels. Does the fact that there are an unlimited number of nestings change the way this would need to work?
HeWhoWas almost 13 years

Yes. Passing the root to the function, and when manually walking the lists I find what I'm looking for at node.children[0].children[1].children[1].children[0]
HeWhoWas almost 13 years

Sorry, you're right, it does work. A spelling error tripped me up :-P Serves me right for using 2 variables of such similar names. It works perfectly, thank you for the help :-)
HeWhoWas almost 13 years

I'm sorry, I don't seem to have enough reputation to talk in chat! I was just ducking in to re-iterate what's posted above, thanks for taking the time to help
HeWhoWas almost 13 years

Would you be able to assist me with returning the parent item of the one that's found? Thanks, in advance :-)
Ramzy Abourafeh about 10 years

How can I got the parent?