CODEWITHSUNDEEP
c#linqdata-structurestree
Tono Nam
Tono Nam

Reputation: 36080

Find node when traversing tree

I want to implement a method that will enable me to find a node in a tree. The way I do it is recursively using global variables to know when to stop.

I have the class:

class Node    // represents a node in the tree
{ 
     // constructor
     public Node() {
          Children = new List<Node>();
     }

     public List<Node> Children; 
     public string Name;
     public string Content;            
}

And the method I have right now is:

    private bool IsNodeFound = false; // global variable that I use to decide when to stop

    // method to find a particular node in the tree
    private void Find(Node node, string stringToFind, Action<Node> foundNode)
    {
        if(IsNodeFound)
           return;

        if (node.Content.Contains(stringToFind)){
            foundNode(node); 
            IsNodeFound =true;               
        }

        foreach (var child in node.Children)
        {
            if (child.Content.Contains(stringToFind)){
                foundNode(node);
                IsNodeFound =true;               
            }

            Find(child, stringToFind, foundNode);
        }

    }

and the way I use the Find method is like:

   // root is a node that contain children and those children also contain children
   // root is the "root" of the tree
   IsNodeFound =false;
   Node nodeToFind = null;
   Find(root, "some string to look for", (x)=> nodeToFind=x);

So my question is how can I make this method more elegant. I will like the signature of the method to look like:

   public Node FindNode(Node rootNode);

I think it is to redundant what am I doing and there is probably a better way of creating that method. Or perhaps I could alter the Node class so that I can achieve the same thing with a linq query.

Upvotes: 10

Views: 22473

Answers (6)

Ani
Ani

Reputation: 113472

I would do it this way:

Write an instance method to generate a subtree of a node (you could make it an extension if you don't control the Node class):

public IEnumerable<Node> GetNodeAndDescendants() // Note that this method is lazy
{
     return new[] { this }
            .Concat(Children.SelectMany(child => child.GetNodeAndDescendants()));    
}

Then you can just find nodes with a little bit of LINQ:

var foundNode = rootNode.GetNodeAndDescendants()
                        .FirstOrDefault(node => node.Content.Contains(stringToFind));

if(foundNode != null)
{
    DoSomething(foundNode);
}

Upvotes: 18

Juan Ayala
Juan Ayala

Reputation: 3528

Recursion, and PLinq

    private Node Find(Node node, Func<Node, bool> predicate)
    {
        if (predicate(node))
            return node;

        foreach (var n in node.Children.AsParallel())
        {
            var found = Find(n, predicate);
            if (found != default(Node))
                return found;
        }
        return default(Node);
    }

And calling code:

     var found = Find(root, (n) => n.Content.Contains("3"));
     if (found != default(Node))
         Console.Write("found '{0}'", found.Name);
     else Console.Write("not found");

Upvotes: 2

Ethan Brown
Ethan Brown

Reputation: 27292

You can either use a depth-first search using recursion (no need for a global variable to know when to terminate):

Node FindNode1( Node rootNode, string stringToFind ) {
    if( rootNode.Content == stringToFind ) return rootNode;
    foreach( var child in rootNode.Children ) {
        var n = FindNode1( child, stringToFind );
        if( n != null ) return n;
    }
    return null;
}

Or, if you wish to avoid recursion, you can accomplish the same thing non-recursively with a stack:

Node FindNode2( Node rootNode, string stringToFind ) {
    var stack = new Stack<Node>( new[] { rootNode } );
    while( stack.Any() ) {
        var n = stack.Pop();
        if( n.Content == stringToFind ) return n;
        foreach( var child in n.Children ) stack.Push( child );
    }
    return null;
}

Upvotes: 3

Kevin DiTraglia
Kevin DiTraglia

Reputation: 26078

If the linq answers confuse you as much as me, here's how I would do it with simple recursion. Note it's depth first, you might want to change it to breadth first if that makes more sense for your model.

public Node FindNode(Node rootNode)
{
    if (rootNode.Content.Contains(stringToFind))
       return rootNode;

    foreach (Node node in rootNode.Children)
    {
        if (node.Content.Contains(stringToFind))
           return node;
        else
           return FindNode(node);
    }

    return null;
}

Upvotes: 2

Ryan
Ryan

Reputation: 8005

You can use one of the other answers that use Linq, or you can use a depth-first search mechanism using recursion:

public Node Find(string stringToFind)
{
    // find the string, starting with the current instance
    return Find(this, stringToFind);
}

// Search for a string in the specified node and all of its children
public Node Find(Node node, string stringToFind)
{
    if (node.Content.Contains(stringToFind))
        return node;

    foreach (var child in node.Children) 
    { 
        var result = Find(child, stringToFind);
        if (result != null)
            return result;
    }

    return null;
}

Upvotes: 16

Alexei Levenkov
Alexei Levenkov

Reputation: 100620

Consider making LINQ-like API: split "Find" and "Act" parts to make it simple. You may not even need any special custom code for "Act" part, existing LINQ will do. 

public IEnumerable<Node> Where(Func<Node, bool> condition);

Depending on your needs you may either walk whole tree once and check each node to implement Where, or do it properly with lazy iteration. For lazy iteration you'll need some sort of structure which remembers current position (i.e. stack of nodes to visit and index of child).

Note: please avoid using global variables. I.e. in your current code simply returning true/false from Find function and stopping iteration when true is returned would be better approach.

Upvotes: 0

Related Questions