Function which will return particular node from tree structure

Question

I am writing the function which will return particular node from tree structure. But when I search in a tree using LINQ it is searching in the first branch and finally when it reaches to leaf it is throwing null reference exception as leaf don't have any child.

Here is my class,

public class Node
    {
        public int Id { get; set; }
        public string Name { get; set; }
        public string Content { get; set; }
        public IEnumerable<Node> Children { get; set; }
        public IEnumerable<Node> GetNodeAndDescendants() // Note that this method is lazy
        {
            return new[] { this }
                   .Concat(Children.SelectMany(child => child.GetNodeAndDescendants()));
        }
    }

This is how I am calling this function,

 var foundNode = Location.GetNodeAndDescendants().FirstOrDefault(node => node.Name.Contains("string to search"));

OR

var foundNode = Location.GetNodeAndDescendants().FirstOrDefault(node => node.Id==123)

What would be the correct way to do this? and any sample code would be grateful

Why do you let your code run into a NullReferenceException in the first place? Shouldn't a leaf return a Children collection with zero elements instead of null, thus avoiding a NullReferenceException? No code sample necessary -- just look at the stack trace of your NullReferenceException to see what causes it, then work from there to figure out how to correct your code's behavior... — , Aug 15 '15 at 13:39

Jason Boyd · Answer 1 · 2015-08-15T22:31:20.157

If you don't mind taking a dependency on a third party solution I have a lightweight library that I have been working on that can do this and many other things with just about any tree. It is called Treenumerable. You can find it on GitHub here: https://github.com/jasonmcboyd/Treenumerable; and the latest version (1.2.0 at this time) on NuGet here: http://www.nuget.org/packages/Treenumerable. It has good test coverage and seems to be stable.

It does require that you create a helper class that implements an ITreeWalker interface with two methods: TryGetParent and GetChildren. As you might guess TryGetParent gets a node's parent so your Node class would have to be modified in a way that it is aware of its parent. I guess you could just throw a NotSupported exception in TryGetParent as that method is not necessary for any of the traversal operations. Anyway, regardless of which way you go the following code would do what you want:

ITreeWaler<Node> walker;
// Don't forget to instantiate 'walker'.

var foundNode =
    walker
    .PreOrderTraversal(Location)
    .FirstOrdefault(node => node.Name.Contains("string to search"));

One difference worth mentioning between my implementation and yours is that my implementation does not rely on recursion. This means you don't have to worry about a deep tree throwing a StackOverflowException.

score 0 · Accepted Answer · edited May 23 '17 at 11:52

Nothing wrong to write your own function, but implementation based on LINQ or recursive iterator is not a good idea (performance!). But why depending on external libraries? A lot of code that you don't need, implementing interfaces, modifying your classes etc. It's not hard to write a generic function for pre-order tree traversal and use it for any tree structure. Here is a modified version of my participation in How to flatten tree via LINQ? (nothing special, ordinary iterative implementation):

public static class TreeHelper
{
    public static IEnumerable<T> PreOrderTraversal<T>(T node, Func<T, IEnumerable<T>> childrenSelector)
    {
        var stack = new Stack<IEnumerator<T>>();
        var e = Enumerable.Repeat(node, 1).GetEnumerator();
        try
        {
            while (true)
            {
                while (e.MoveNext())
                {
                    var item = e.Current;
                    yield return item;
                    var children = childrenSelector(item);
                    if (children == null) continue;
                    stack.Push(e);
                    e = children.GetEnumerator();
                }
                if (stack.Count == 0) break;
                e.Dispose();
                e = stack.Pop();
            }
        }
        finally
        {
            e.Dispose();
            while (stack.Count != 0) stack.Pop().Dispose();
        }
    }
}

and your function inside the class Node becomes:

public IEnumerable<Node> GetNodeAndDescendants() // Note that this method is lazy
{
    return TreeHelper.PreOrderTraversal(this, node => node.Children);
}

Everything else stays the way you did it and should work w/o any problem.

EDIT: Looks like you need something like this:

public interface IContainer
{
    // ...
}

public class CustomerNodeInstance : IContainer
{
    // ...
}

public class ProductNodeInstance : IContainer
{
    // ...
}

public class Node : IContainer
{
    // ...
    public IEnumerable<IContainer> Children { get; set; }
    public IEnumerable<IContainer> GetNodeAndDescendants() // Note that this method is lazy
    {
        return TreeHelper.PreOrderTraversal<IContainer>(this, item => { var node = item as Node; return node != null ? node.Children : null; });
    }
}

The problem with me now is leaf nodes of tree are going to be other than of Type Node , it can be of type CustomerNodeInstance or ProductNodeInstance All types(CustomerNodeInstance,Node,ProductNodeInstance ) are implementing IContainer interface. So Either child can be Instance or Node. Is there any better way of doing that. — , Aug 17 '15 at 15:37
do CustomerNodeInstance and ProductNodeInstance inherit from Node? And what does IContainer interface look like? — Ivan Stoev, Aug 17 '15 at 16:01
No, CustomerNodeInstance and ProductNodeInstance does not inherit from node but they are implementing interface IContainer. So , Node, CustomerNodeInstance and ProductNodeInstance implements IContainer. And IContainer has ContainerType enum which states its type , whether it is of type Node or CustomerNodeInstance or ProductNodeInstance. — , Aug 17 '15 at 17:20
if I understand correct, you want these leaf nodes to be included in the function result. I'm pretty sure it's possible, but shouldn't then `Node.Children` property be of type `IEnumerable`? — Ivan Stoev, Aug 17 '15 at 17:48
Yes, its correct. Node has its children as IEnumerable and Node can has Node, CustomerNodeInstance and ProductNodeInstance as children. So, Node can can has multiple nodes or Nodes+CustomerNodeInstance or Nodes+CustomerNodeInstance+ProductNodeInstance or CustomerNodeInstance+ProductNodeInstance or etc. as children. Unfortunately I didn't get any proper solution. Currently I am just using stack(push/pop) which is killing performance. — , Aug 17 '15 at 17:55
Thanks a lot @Ivan Stoev :). It is working like a charm and saved my time. — , Aug 17 '15 at 18:59

Function which will return particular node from tree structure

2 Answers2

Linked